BSEARCH1 - Binary search

You are given a sorted array of numbers, and followed by number of queries, for each query if the queried number is present in the array print its position, else print -1.

Input

First line contains N Q, number of elements in the array and number of queries to follow.

Second line contains N numbers, the elements of the array. Each number will be -10^9 <= ai <= 10^9, 0 < N <= 10^5, 0 < Q <= 5*10^5

Output

For each element in the query, print the elements 0 based location of its first occurence, if present, otherwise print -1.

Example

Input:
5 4
2 4 7 7 9
7
10
4
2

Output:
2
-1
1
0

Added by:jack(chakradarraju)
Date:2012-03-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:NITT Class

hide comments
2020-04-18 06:11:52
Pythonists submit in PyPy, it's possible to get AC here. The input is huge, 500000 integers, so ensure your I/O is up to the task as well -> https://www.spoj.com/ranks/INTEST/lang=PYTH%203.2.3
2020-04-18 03:21:07 Rafael Godoi
TLE for Python. Don't waste your time.
2019-12-15 19:03:06
this website does'nt accepts cin & cout.
untill u use scanf n printf they will show TLE
2018-10-12 18:19:09
My code runs fine on other IDEs. Why is it returning error SIGSEV something?
<snip>

Last edit: 2023-05-12 09:11:27
2018-06-30 22:19:21
read the comments till end.
2018-06-12 13:19:18
hint : lower_bound gives the iterator to the first element in the array that is equal or GREATER than the number being searched . ( so you could get a valid index in return even though the element would not be present in the array, so you need to check if the iterator points to the number actually being searched to validate the answer )
2018-05-29 03:15:19
Go to hell this stupid TLE thing, just because I didn't write scanf and printf.
2017-12-27 15:30:02
Simple binary search and arrays worked for me along with scanf/printf
2017-10-11 21:16:17
it is giving run time error..how can i remove it?
2017-09-06 17:59:01
Remember: it's a SORTED vector as input.
I've ignored that and got TLE.

Last edit: 2017-09-06 18:00:39
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.