A Binary Search Problem


Submit solution

Points: 7
Time limit: 2.0s
PyPy 3 3.0s
Python 3 5.0s
Memory limit: 256M

Author:
Problem type

Given a sorted array, \(A\), consisting of \(N\) integers, and \(Q\) queries, each consisting of a single integer \(X\), output the leftmost index of \(X\) in \(A\) (\(1\)-indexed), or \(-1\) if \(A\) does not contain \(X\).

Input Specification

The first line will contain a single integer \(N \le 10^5\), denoting the size of \(A\).

The second line will contain \(N\) integers, \(-10^9 \le A_i \le 10^9\), denoting the elements of \(A\).

The third line will contain a single integer \(Q \le 10^5\), denoting the number of queries.

The following \(Q\) lines will each contain a single integer \(X\), \(-10^9 \le X \le 10^9\).

Output Specification

Output \(Q\) lines, the \(ith\) line denoting the leftmost \(1\)-indexed position of \(Q_i\) in \(A\) (or \(-1\) if it is not present).

Sample Input 1

3
1 2 2
3
1
2
0

Sample Output 1

1
2
-1

Comments

There are no comments at the moment.