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
2015-08-25 06:36:49
yes got accepted when i used 1st occurence concept.
2015-08-11 19:08:10
how i can optimize this more
<snip>

Last edit: 2023-05-12 09:12:17
2015-04-01 02:44:17 bestknighter
After 3 days of a lot of optimizations, I did it right. It wasn't exactly a binary search, all printings were at the end of the program, I used long int and printf, scanf. Got 0.22s. From TLE to AC... PHEW!
2015-03-26 09:18:48 karan
i mean WHAT THE HELL.. iostream why are u so slow.. i am never going to use u again.. tried around 7 different methods using maps as well in such a simple problem.. problem lied in i/o method.. Bjarne,man why u made c++ so slow..

Last edit: 2015-03-26 09:19:30
2015-01-26 10:31:38 Madhav
pay attention to the first occurence!!
2014-12-30 23:47:44 Leandro de Andrade Moura [UFPE]
Attention to negative values!
2014-10-13 22:41:08 CHANDAN KUMAR
<snip>
please tell me what is going wrong with my code please help me is it stackoverflow or something else
at 6th test case it is showing wrong answer

Last edit: 2023-05-12 09:12:40
2014-08-15 18:46:57 Asheesh Pathak
Learned something new! :D


Last edit: 2014-08-15 18:56:55
2014-06-17 22:14:35 shade_1
WA after test case 6 although i am printing first occurrence of the number and using long long .
2014-05-25 21:18:52 Raphael GuimarĂ£es
Pay attention to sequences like:
1 2 2 3 4
The first occurence is 1!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.