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
2017-08-27 22:27:46
python is giving TLE :(
how can i remove it..
2017-08-25 23:17:41
can use map..AC in 0.29 seconds
2017-07-30 21:12:27
I tried python but got TLE in C++ I got AC with printf and scanf
2017-05-16 09:34:10
It's Seems easy at first,Unless TLE starts popping out on your screen.
Some Tips:
Dont use lower_bound,it will give TLE.
Don't use Fast I/O Technique,Use printf scanf in C++.
Just pass Test case 6.That is benchmark here :p
2017-02-09 03:44:06
Your solution should print first occurrence of target element. Also use scanf and printf in C++ to beat TLE
2016-07-08 14:39:05
lower bound giving Wrong dont know y but when implemented on my own gives all A.C
2016-04-07 22:34:20
I find the input solution, but my code can't be submited
<snip>

Last edit: 2023-05-12 09:12:10
2016-02-15 12:53:34 sharif ullah
I think lower_bound() function causes wrong answer
2016-02-02 22:12:40
if there is repetition then you need to print the least index
as search(2) in 1 2 2 2 2 2 2 2 3 4 25 is 1
2015-09-16 23:58:57 Sagar Kar
hint for tle: Use scanf and printf..... yes it makes difference here
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.