## 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 occurence 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 occurence 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