BBIN2 - Búsqueda Binaria 2


Given an array of N integers in non-decreasing order, you're going to receive Q queries. Each of them contains a single integer. For each query use binary search to respond with the index of the last occurrence of the given integer in the array.

Input

In the first line there is an integer N (1 <= N <= 10^5) and an integer Q (1 <= Q <= 10^5).

In the second line, N integers separated by a single space. Each integer takes a values between 1 and 10^9.

Then Q lines follows, each one with an integer between 1 and 10^9, representing a query.

Output

For each query (in the same order they were given) print a line with a single integer, the index of the last occurrence of the corresponding element, or -1 if it is not in the given array.

Example

Input:
10 4
1 3 4 5 5 6 7 8 8 17
3 
5 
9
1

Output:
1
4
-1
0

hide comments
solvertobe: 2019-06-29 08:12:03

Easy binary search. What if it's required to find the index of the i_th occurrence of some x, if there isn't i_th copy of x then print say -1. Will binary search work ?

Last edit: 2019-06-29 08:16:07

Added by:BerSub
Date:2016-09-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU