Truy vấn k (K-query)

Nguồn: SPOJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $a_1,a_2,\ldots,a_n$. Mỗi truy vấn gồm ba số $i,j,k$. Với từng truy vấn, hãy đếm số phần tử lớn hơn $k$ trong đoạn $a_i,a_{i+1},\ldots,a_j$.

Dữ liệu vào

Dòng đầu chứa $n$. Dòng thứ hai chứa $n$ số $a_i$. Dòng thứ ba chứa $q$. Mỗi trong $q$ dòng tiếp theo chứa $i,j,k$.

Kết quả

Với mỗi truy vấn, in số phần tử lớn hơn $k$ trong đoạn $[i,j]$ trên một dòng.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n\le 30000$
• $1\le q\le 200000$
• $1\le a_i,k\le 10^9$
• $1\le i\le j\le n$

Ví dụ

Input

5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2

Output

2
0
3

Giải thích

Ở truy vấn 2 4 1, đoạn là [1,2,3]; hai giá trị 2,3 lớn hơn $1$. Truy vấn 4 4 4 chỉ có giá trị $3$, nên kết quả là $0$.