Cho mảng ~A~ gồm ~n~ số nguyên ~A[1], A[2], \dots, A[n]~. Có ~Q~ truy vấn độc lập, truy vấn thứ ~i~ cho ba số nguyên ~L, R, K~.

Yêu cầu: Với mỗi truy vấn ~(L, R, K)~, hãy đếm số phần tử của đoạn ~A[L \dots R]~ có giá trị không vượt quá ~K~ (nghĩa là đếm số chỉ số ~j~ thỏa ~L \le j \le R~ và ~A[j] \le K~).

Input

• Dòng 1 chứa hai số nguyên dương ~n, Q~ (~n, Q \le 2 \cdot 10^5~);

• Dòng 2 chứa ~n~ số nguyên dương ~A[1], A[2], \dots, A[n]~ (~A[i] \le 10^9, 1 \le i \le n~);

• ~Q~ dòng tiếp theo, dòng thứ ~t~ chứa ba số nguyên dương ~L, R, K~ tương ứng truy vấn thứ ~t~ (~L \le R \le n, K \le 10^9, 1 \le t \le Q~).

Các số ghi trên cùng dòng cách nhau bởi một dấu cách.

Output

Gồm ~Q~ dòng, dòng thứ ~t~ ghi một số nguyên duy nhất là số lượng phần tử của đoạn ~A[L \dots R]~ có giá trị không vượt quá ~K~ của truy vấn thứ ~t~.

Scoring

Sample Input 1

6 2
1 2 3 6 5 3
2 5 3
3 3 2

Sample Output 1

2
0