Sequence and Queries 1

Time limit1sMemory limit512 MB

Summary

Given a static sequence, answer M queries counting how many values in range A[i..j] are greater than k.

Level: Hard8 of 10
Topics: Segment tree, Sorting, Binary search, Divide and conquer
Solved: No attempts yet

Problem

You are given a sequence $A_1, A_2, \dots, A_N$ of length $N$ . Write a program that processes the following query.

i j k: print how many elements among $A_i, A_{i+1}, \dots, A_j$ are greater than $k$ .

Input

The first line contains the size of the sequence, $N$ . ( $1 \le N \le 100000$ )

The second line contains $A_1, A_2, \dots, A_N$ separated by spaces. ( $1 \le A_i \le 10^9$ )

The third line contains the number of queries, $M$ . ( $1 \le M \le 100000$ )

Each of the next $M$ lines contains one query as $i$ , $j$ , $k$ in that order. ( $1 \le i \le j \le N$ , $1 \le k \le 10^9$ )

Output

Print the answer to each query on its own line, in the order the queries are given.

Examples7

Example 1
Input
```
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
```
Expected output
```
2
0
3
```
Example 2
Input
```
1
1
3
1 1 1
1 1 1000000000
1 1 1
```
Expected output
```
0
0
0
```

Example 3

Input

6
7 7 7 7 7 7
5
1 6 6
1 6 7
1 6 8
3 3 7
2 5 1

Expected output

Example 4

Input

5
1000000000 1 1000000000 1 1000000000
6
1 5 999999999
1 5 1000000000
1 5 1
2 4 999999999
5 5 999999999
1 1 1000000000

Expected output

Example 5

Input

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20
1 20 1
1 20 2
1 20 3
1 20 4
1 20 5
1 20 6
1 20 7
1 20 8
1 20 9
1 20 10
1 20 11
1 20 12
1 20 13
1 20 14
1 20 15
1 20 16
1 20 17
1 20 18
1 20 19
1 20 20

Expected output

Example 6

Input

20
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
20
1 20 10
2 20 10
3 20 10
4 20 10
5 20 10
6 20 10
7 20 10
8 20 10
9 20 10
10 20 10
11 20 10
12 20 10
13 20 10
14 20 10
15 20 10
16 20 10
17 20 10
18 20 10
19 20 10
20 20 10

Expected output

Example 7

Input

12
3 3 2 2 2 1 3 4 5 5 2 2
15
9 9 3
1 8 2
4 12 4
3 8 3
2 3 5
5 12 2
4 7 1
2 5 6
9 12 5
12 12 1
12 12 6
6 12 1
2 11 4
2 10 1
5 12 6

Expected output