Monk and his friend Micro are on a quest to find the answer of Life, Universe and Everything. In order to complete it they need to answer $$Q$$ queries on an array $$A$$ having $$N$$ integers. The queries can be of following two types:
$$0 \space x:$$ Find the number of numbers in $$A$$ which are not less than $$x$$.
$$1 \space x:$$ Find the number of numbers in $$A$$ which are greater than $$x$$.
Help them complete the quest and be back in time for the next Code Monk Challenge.

Input Format:
First line consists of a single integer denoting $$N$$.
Second line consists of $$N$$ space separated integers denoting the array $$A$$.
Third line consists of a single integer denoting $$Q$$.
Each of the following $$Q$$ lines consists of a query of one of the given two types.

Output Format:
For each query print the required answer in new line.

Constraints:
$$1 \le N \le 10^5$$
$$1 \le Q \le 3 \times 10^5$$
$$1 \le A[i], x \le 10^9$$

SAMPLE INPUT

SAMPLE OUTPUT

0
1
2

Explanation

For first query, there are no numbers in the array which are not less than $$5$$ so answer for first query is $$0$$.
For second query, $$4$$ is the only number greater than $$3$$, so answer is $$1$$.
For third query, $$3$$ and $$4$$ are the numbers in array which are not less than $$3$$, so answer is $$2$$.

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

Binary Search, Easy, Easy

CODE EDITOR

Contributor

This Problem was Asked in

All Tracks Algorithms Searching Binary Search Problem

Binary Search, Easy, Easy

CODE EDITOR

Contributor

This Problem was Asked in

Social Share