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
2014-05-20 17:15:14 kelaseek
int index is giving you wrong answer
2014-04-22 18:50:10 SHIVAM DIXIT
1.use scanf,printf
2. use long long for array elements and indices also....
rest is easy.......

Last edit: 2014-04-22 18:53:24
2014-03-01 21:27:41 Revti Raman Singh
guys use scanf and printf instead of cin and cout !
2013-10-19 23:46:01 miczegla
I'm getting WA at 6th test could someone look at my code at help me find problem http://ideone.com/0HseRw
2013-10-19 08:11:02 Suhas
For future reference: a simplistic (no optimization) binary search with C++'s I/O(cin, cout) will probably give a TLE on 6.
Use C I/O (scanf, printf) to get it accepted.
Deplorable, the kind of practices problems like these encourage...
There ought be a 'recommended' language, or the time limit should be more accommodating.
2013-06-08 16:04:52 shashank nagamalla
I am getting WA after 6th test case and i am printing first occurrence of the number.
2013-05-29 07:20:20 Mostafa 36a2
for all who gets WA
Print only the first occurence of the number.
2013-03-17 19:38:42 Smirnova Natalia
Is there a possibility that input file contains empty lines between other lines? Do I have to add empty lines between lines when outputting the answers?

Last edit: 2013-03-17 19:39:08
2013-02-26 15:01:54 Jacek
what is a better option ?
2013-02-06 21:53:50 Paul Draper
FYI, a binary search is not the best way to do this.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.