Nhiên liệu

Một công ty vận tải theo dõi giá bán nhiên liệu trong \(N\) ngày, tạo thành dãy \(a_1, a_2, \ldots, a_N\).

Vì là khách hàng quen, công ty được ưu đãi như sau.
Gọi \(p_i\) là giá thực trả ở ngày \(i\):
$
p_1 = a_1,\qquad p_i = \min(p_{i-1}, a_i)\ \ \text{với}\ i \ge 2.
$
Nói cách khác, nếu giá công bố ngày \(i\) cao hơn giá đã mua ở ngày \(i-1\) thì công ty vẫn được mua với giá ngày \(i-1\).

Có \(q\) truy vấn dạng \((L, R, x)\): trong các ngày từ \(L\) đến \(R\), có bao nhiêu ngày công ty mua nhiên liệu với giá thực trả đúng bằng \(x\)?

Input

• Dòng \(1\) chứa số nguyên \(N\).
• Dòng \(2\) chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\).
• Dòng \(3\) chứa số nguyên \(q\).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L, R, x\).

Output

Ghi ra \(q\) dòng, dòng thứ \(t\) là kết quả của truy vấn thứ \(t\).

Giới hạn

• \(1 \le N \le 2 \cdot 10^5\)
• \(1 \le q \le 2 \cdot 10^5\)
• \(1 \le a_i \le 10^9\)
• \(1 \le L \le R \le N\)
• \(1 \le x \le 10^9\)

Scoring

• Subtask 1 (70%): \(N, q \le 10^3\).
• Subtask 2 (30%): Không có ràng buộc gì thêm.

Input

8
12 15 10 11 9 20 8 8
3
3 7 8
5 8 12
2 5 10

Output

1
0
2