길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$이 주어진다. 수열의 모든 수는 $1$ 이상 $N$ 이하이며 서로 다르다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• l r k: 부분배열 $[A_l, A_{l+1}, \ldots, A_r]$ 을 $k$만큼 오른쪽으로 시프트한다. 고로, $A_l$ 은 $A_{l+k}$, $A_{r-k}$ 는 $A_r$, $A_{r-k+1}$ 은 $A_l$, $A_r$ 은 $A_{l+k-1}$ 이 된다. 이후, 수열에 길이 $3$의 증가하는 부분 수열 (subsequence) 이 있다면 YES, 아니면 NO를 출력한다.

입력

첫째 줄에 수열의 크기 $N$이 주어진다. ($1 \le N \le 120{,}000$)

둘째 줄에는 $A_1, A_2, \ldots, A_N$이 주어진다. 모든 수는 서로 다르다. ($1 \le A_i \le N$)

셋째 줄에는 쿼리의 개수 $M$이 주어진다. ($1 \le M \le 120{,}000$)

넷째 줄부터 $M$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. ($1 \le L \le R \le N$, $0 \le K \le R-L+1$)

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

Sample

Input

6
2 5 6 1 3 4
1
1 6 5

Output

YES

Sample

Input

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

Output

YES
YES
YES
YES

Sample

Input

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

Output

NO
YES

Sample

Input

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

Output

NO
NO
YES