The Basic One !!!!

0

0 votes
Binary Search, Easy
Problem

Milkha Singh has to impress his girlfriend. To do that, he has to pass a maze Q amount of times in his first try every time. The maze consists of N-doors with a different no on each door. There is only one exit door X with a specific no on it for every time he enters the maze. The maze manager is his friend and tells him the door no but he cannot see the number of the door unless he enters it and once he enters,he loses. Help him win by telling the index of the door he needs to enter to impress his girlfriend.

Note:- The door no's may not be in sorted order If so, Then Milkha's friend arranges them and then the index of correct door might change but Milkha's friend also has asked you to arrange that for him

INPUT FORMAT The first line contains N denoting the amount of doors in the maze The next line contains N space separated integers denoting the number on that door The next line contains Q and then the next Q lines follow containing X, the exit door no.

OUTPUT FORMAT Output the index of exit door in a new line

CONSTRAINTS

1≤N≤10^5

1≤Door no ≤10^9

1≤Q≤10^5

1≤X≤10^9

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?