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
surya97: 2015-08-25 06:36:49

yes got accepted when i used 1st occurence concept.

hassangarh: 2015-08-11 19:08:10

how i can optimize this more
<snip>

Last edit: 2023-05-12 09:12:17
bestknighter: 2015-04-01 02:44:17

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!

karan: 2015-03-26 09:18:48

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
Madhav: 2015-01-26 10:31:38

pay attention to the first occurence!!

Leandro de Andrade Moura [UFPE]: 2014-12-30 23:47:44

Attention to negative values!

CHANDAN KUMAR: 2014-10-13 22:41:08

<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
Asheesh Pathak: 2014-08-15 18:46:57

Learned something new! :D

Last edit: 2014-08-15 18:56:55
shade_1: 2014-06-17 22:14:35

WA after test case 6 although i am printing first occurrence of the number and using long long .

Raphael GuimarĂ£es: 2014-05-25 21:18:52

Pay attention to sequences like:
1 2 2 3 4
The first occurence is 1!


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