First Index

Problem Description

You are given an array A of length N. You need to solve Q queries. In each query, you will be given an integer B[i] and you need to find the index of the element which is at least B[i]. If there are several such indexes, return the minimum such index. Return -1 if no such index exists.

Note- The array is 0 indexed.

Problem Constraints

1 <= N,Q <= 5 x 10⁵

1 <= A[i], B[i] <= 10⁹

Input Format

The first argument contains an integer array A of length N.

The second argument contains an integer array B of length Q, denoting the queries.

Output Format

Return an array of length Q, containing the answer to the queries.

Example Input

Input 1:

  A : [ 9, 1 ]
  B : [ 7, 10, 3 ]

Input 2:

   A : [ 2, 3, 4 ]
  B : [ 2, 3, 4 ]

Example Output

Output 1:

  [0, -1, 0]

Output 2:

  [0, 1, 2]

Example Explanation

Explanation 1:

  The first element 9 is greater than 7 and 3. No element greater than 10 exists.

Explanation 2:

  Since the queries and array are same, the answer will the index of the element.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a question? Checkout Sample Codes for more details.

Start solving First Index on Interview Code Editor

Hints

Hint 1
Solution Approach
Complete Solution

First Index

Discussion