Problems
Interval Less Query
Interval Less Query
Given an array of size $n$, answer $q$ queries of the next kind: how many numbers on interval $[l, r]$ have value less than $x$.
\InputFile
The first line contains the size $n\:(1 \le n \le 2 \cdot 10^5)$ of array. The next line contains $n$ integers. Number of queries $q\:(1 \le q \le 10^5)$ is given in the next line. Each of the next $q$ lines contains one query: three integers $l, r$ and $x\:(l \le r, 1 \le x \le 10^9)$.
\OutputFile
For each query print in a separate line how many numbers on $[l, r]$ have value less than $x$.
Input example #1
8 1 3 2 4 3 10 5 5 4 1 8 5 1 4 3 5 8 9 2 6 4
Output example #1
5 2 3 3