Input

The first line contains an integer $N$, the length of the sequence. ($1 \le N \le 120{,}000$)

The second line contains $N$ integers $A_1, A_2, \ldots, A_N$, all distinct. ($1 \le A_i \le N$)

The third line contains an integer $M$, the number of queries. ($1 \le M \le 120{,}000$)

The next $M$ lines each contain a query in the format $l$ $r$ $k$. ($1 \le L \le R \le N$, $0 \le K \le R-L+1$)

Output

For each query, output a single line containing YES or NO.

Examples

Input 1

6
2 5 6 1 3 4
1
1 6 5

Output 1

YES

Input 2

8
5 1 2 8 7 6 3 4
4
2 4 2
4 5 1
1 3 2
3 8 2

Output 2

YES
YES
YES
YES

Input 3

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

Output 3

NO
YES

Input 4

6
6 5 4 3 2 1
3
1 1 0
1 3 1
2 5 3

Output 4

NO
NO
YES

Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$. All numbers in the sequence are integers between $1$ and $N$ and are distinct. Write a program to process the following queries:

• l r k: right-rotate the subarray $[A_l, A_{l+1}, \ldots, A_r]$ by $k$ positions. That is, $A_l$ becomes $A_{l+k}$, $A_{r-k}$ becomes $A_r$, $A_{r-k+1}$ becomes $A_l$, and $A_r$ becomes $A_{l+k-1}$. Then determine whether the whole sequence contains an increasing subsequence of length $3$ (a subsequence, not necessarily contiguous). If it does, output YES; otherwise, output NO.