Sequence and Queries 35

Time limit7sMemory limit512 MB

Summary

Given a permutation, each query rotates a subarray right by k positions, then asks whether the array has an increasing subsequence of length 3.

Level: Hard8 of 10
Topics: Segment tree, Array, Implementation
Solved: No attempts yet

Problem

A sequence $A_1, A_2, \ldots, A_N$ of length $N$ is given. Every number in the sequence is between $1$ and $N$ inclusive, and all numbers are distinct. Write a program that processes the following query.

l r k: Shift the subarray $[A_l, A_{l+1}, \ldots, A_r]$ right 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}$ . After the shift, print YES if the sequence contains an increasing subsequence of length 3, and NO otherwise.

Input

The first line contains the size $N$ of the sequence. ( $1 \le N \le 120,000$ )

The second line contains $A_1, A_2, \ldots, A_N$ . All numbers are distinct. ( $1 \le A_i \le N$ )

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

The next $M$ lines each contain one query. ( $1 \le L \le R \le N$ , $0 \le K \le R-L+1$ )

Output

Print the result of each query on its own line.

Examples4

Example 1
Input
```
6
2 5 6 1 3 4
1
1 6 5
```
Expected output
```
YES
```

Example 2

Input

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

Expected output

YES
YES
YES
YES

Example 3
Input
```
5
4 3 2 5 1
2
3 4 1
1 2 1
```
Expected output
```
NO
YES
```

Example 4

Input

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

Expected output

NO
NO
YES