BSEARCH1 - Binary search

no tags 

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

hide comments
SHIVAM DIXIT: 2014-04-22 18:50:10

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
Revti Raman Singh: 2014-03-01 21:27:41

guys use scanf and printf instead of cin and cout !

miczegla: 2013-10-19 23:46:01

I'm getting WA at 6th test could someone look at my code at help me find problem http://ideone.com/0HseRw

Suhas: 2013-10-19 08:11:02

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.

shashank nagamalla: 2013-06-08 16:04:52

I am getting WA after 6th test case and i am printing first occurrence of the number.

Mostafa 36a2: 2013-05-29 07:20:20

for all who gets WA
Print only the first occurence of the number.

Smirnova Natalia: 2013-03-17 19:38:42

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
Jacek: 2013-02-26 15:01:54

what is a better option ?

Paul Draper: 2013-02-06 21:53:50

FYI, a binary search is not the best way to do this.


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