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
a_kk: 2017-08-27 22:27:46

python is giving TLE :(
how can i remove it..

dunjen_master: 2017-08-25 23:17:41

can use map..AC in 0.29 seconds

robertohonda: 2017-07-30 21:12:27

I tried python but got TLE in C++ I got AC with printf and scanf

rohit9934: 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

kaiser123: 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

akhileshsoni96: 2016-07-08 14:39:05

lower bound giving Wrong dont know y but when implemented on my own gives all A.C

grfer96: 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
sharif ullah: 2016-02-15 12:53:34

I think lower_bound() function causes wrong answer

krishna_at1996: 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

Sagar Kar: 2015-09-16 23:58:57

hint for tle: Use scanf and printf..... yes it makes difference here


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