Fredo and Large Numbers
Tag(s):

## Ad-Hoc, Data Structures, Easy-Medium, data compression

Problem
Editorial
Analytics

Fredo is pretty good at dealing large numbers. So, once his friend Zeus gave him an array of N numbers , followed by Q queries which he has to answer. In each query , he defines the type of the query and the number f for which Fredo has to answer. Each query is of the following two types:
Type 0: For this query, Fredo has to answer the first number in the array (starting from index 0) such that its frequency is atleast equal to f.
Type 1: For this query, Fredo has to answer the first number in the array such that frequecy is exactly equal to f.
Now, Fredo answers all his queries but now Zeus imagines how he should verify them . So, he asks you to write a code for the same.
Note: If there is no number which is the answer to the query, output 0.
Use fast I/O.

Input :
The first line of the input contains N , the size of the array
The next line contains N space separated integers.
The next line contains Q, denoting the number of queries.
Then follow Q lines, each line having two integers type and f, denoting the type of query and the frequency for which you have to answer the query.

Output:
You have to print the answer for each query in a separate line.

Input Constraints:
$1 \le N \le 10^6$
$1 \le A[i] \le 10^{18}$
$1 \le Q \le 10^6$
$0 \le type \le 1$
$1 \le f \le 10^{18}$

SAMPLE INPUT
6
1 2 2 1 2 3
5
0 1
0 2
1 2
1 3
0 3

SAMPLE OUTPUT
1
1
1
2
2

Explanation

Query 1: 1 is the first number from left with frequency atleast 1.
Query 2: 1 is the first number from left with frequency atleast 2.
Query 3: 1 is the first number from left with frequency exactly 2.
Query 4: 2 is the first number from left with frequency exactly 3.
Query 5: 2 is the first number from left with frequency atleast 3.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Circuits

OTHER PROBLEMS OF THIS CHALLENGE
• Basic Programming > Implementation
• Basic Programming > Implementation
• Algorithms > String Algorithms
• Math > Number Theory