e-olymp
Competitions

ADA University - March 7 - Segment Tree

Interval Less Query

Given an array of size n, answer q queries of kind: how many numbers on [l, r] have value less than x.

Input

The first line contains the size n (1n105) of array. The next line contains n numbers. Number of queries q (1q105) is given in the next line. Each of the next q lines contains one query: three integers l, r and x (lr, 1x109).

Output

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

Time limit 1 second
Memory limit 128 MiB
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