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.
The first line contains the size n(1≤n≤2⋅105) of array. The next line contains n integers. Number of queries q(1≤q≤105) is given in the next line. Each of the next q lines contains one query: three integers l,r and x(l≤r,1≤x≤109).
For each query print in a separate line how many numbers on [l, r] have value less than x.