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

Input

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

Output

For each query print in a separate line how many numbers on $[l,r]$ have value less than $x$.

Examples