Super Mario (Super Mario)

Nguồn: HDU

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

Đề bài

Có $n$ viên gạch nằm tại các vị trí $0,1,\ldots,n-1$; viên gạch ở vị trí $i$ có độ cao $h_i$. Mỗi truy vấn $L,R,H$ hỏi có bao nhiêu viên gạch trong các vị trí $L..R$ có độ cao không vượt quá $H$.

Dữ liệu vào

Dòng đầu chứa $n,m$. Dòng thứ hai chứa $n$ độ cao $h_i$. Mỗi trong $m$ dòng sau chứa $L,R,H$.

Kết quả

Với mỗi truy vấn, in số viên gạch có $h_i\le H$ trong đoạn $[L,R]$.

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,m\le10^5$
• $0\le h_i,H\le10^9$
• $0\le L\le R<n$
• chỉ số của bài này là 0-based

Ví dụ

Input

10 10
0 5 2 7 5 4 3 8 7 7
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3

Output

4
0
0
3
1
2
0
1
5
1

Giải thích

Ở truy vấn đầu, đoạn vị trí $2..8$ có các độ cao [2,7,5,4,3,8,7]; bốn giá trị 2,5,4,3 không vượt quá $6$.