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$.