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
2024-06-13 22:51:24
Que exercício da desgraça. Caso façam em C++, usem o I/O mais rápido. Provavelmente é o motivo do TLE
2024-02-21 17:47:23
Use fast I/O and don't use 'endl' in cpp
2024-01-26 11:39:58
AC in 924812849 go !!
2023-09-06 20:41:08
17*5*100000 operations! Should easily pass within 1sec!
But still got TLE due to cin/cout even after using ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
scanf/printf is here to rescue!
2023-09-02 16:07:10
This problem is bizarre. I used ios_base::sync_with_stdio(false); + cin.tie(NULL); + '\n' instead endl + cin/cout. Check if you take the first occurence of value, this is important.
2023-04-19 20:34:13
I could only make it work by using lower_bound in cpp
2021-10-01 17:31:49
complete waste of time,right code but still showing TLE
2020-12-28 18:26:47
Make sure to use scanf and printf for C++ users. The questions asks for the first occurrence of the interger make sure to read the question properly.
2020-07-22 01:34:23
Turns out vedudx is incorrect. This site DOES accept cin and cout, however you need flush your stream. For example, in this problem you could cout <<endl instead of cout << '\n' to flush stuff every time you make a newline. The best option is to use cout.flush() at the end of the program.

Also, use:
ios_base::sync_with_stdio(false);
cin.tie(NULL);

As it makes cin and cout faster than scanf and printf

Last edit: 2020-07-22 02:36:44
2020-07-08 23:36:06
Make I/O fast, it cost me some WAs.
Easy problem though, simple binary search.


Last edit: 2020-07-08 23:36:30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.