Một công ty vận tải thường xuyên phải mua nhiên liệu để phục vụ hoạt động kinh doanh. Trong \(N\) ngày liên tiếp, giá nhiên liệu được công bố lần lượt là:

Công ty có một chính sách ưu đãi đặc biệt khi mua nhiên liệu:

• Ngày đầu tiên, công ty mua nhiên liệu với đúng giá được công bố.
• Từ ngày thứ \(i\) trở đi, nếu giá công bố ngày đó cao hơn giá đã mua ở ngày trước thì công ty vẫn được mua với giá bằng giá đã mua ở ngày trước.
• Nếu giá công bố ngày đó thấp hơn hoặc bằng giá đã mua ở ngày trước thì công ty được mua theo giá công bố mới.

Nói cách khác, giá thực tế mà công ty phải trả ở ngày thứ \(i\) chính là giá nhỏ nhất trong các giá công bố từ ngày \(1\) đến ngày \(i\).

Để thống kê chi phí hoạt động, công ty đưa ra \(q\) truy vấn. Mỗi truy vấn gồm ba số nguyên \(L, R, x\). Với mỗi truy vấn, hãy cho biết trong các ngày từ ngày \(L\) đến ngày \(R\), có bao nhiêu ngày công ty mua nhiên liệu với giá thực tế đúng bằng \(x\).

Input

• Dòng thứ nhất chứa một số nguyên dương \(N\) (\(1 \le N \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^6\)).
• Dòng thứ ba chứa một số nguyên dương \(q\) (\(1 \le q \le 2 \cdot 10^5\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(L, R, x\) (\(1 \le L \le R \le N, 1 \le x \le 10^6\)).

Output

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

Example

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

1
0
2