Cho dãy số nguyên A độ dài N và Q truy vấn: Mỗi truy vấn là một bộ ba (i, j, k) - yêu cầu đếm số lượng phần tử lớn hơn k nằm trong dãy con ~A_i~, ~A_{i+1}~, ..., ~A_j~ ?

Input

• Dòng đầu tiên chứa 2 số nguyên dương N và Q (1 ≤ N, Q ≤ ~10^5~).
• Dòng thứ hai chứa N số nguyên biểu diễn dãy A (|Ai| ≤ 109). Trong Q dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, k biểu diễn một truy vấn (1 ≤ i ≤ j ≤ N, |k| ≤ ~10^9~).

Output

• Gồm Q dòng, mỗi dòng là kết quả của một truy vấn tương ứng.

Example

Input:

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

Output:

2
0
3