Monk and Search
Tag(s):

## Binary Search, Easy

Problem
Editorial
Analytics

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
4
1 2 3 4
3
0 5
1 3
0 3
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, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Searching)

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Searching
• Algorithms > Searching
• Algorithms > Searching
• Algorithms > Searching