All Tracks Algorithms Searching Binary Search Problem

Monk and Search
Tag(s):

Binary Search, Easy, 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, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Searching)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications