有 $n$ 座摩天大楼排成一排，第 $i$ 座大楼的高度为 $h_i$。这些高度 $h_i$ 构成了一个 $1$ 到 $n$ 的排列。

Alexey 想要使用他的抓钩进行跳跃。为了完成一次跳跃，他需要恰好三座摩天大楼：$i, j, k$，满足 $i < j < k$ 且 $h_i < h_j < h_k$。

此外，摩天大楼有时会改变它们的位置。你需要处理 $q$ 次询问： 在第 $i$ 次询问中，给定 $l_i, r_i, k_i$。对于所有满足 $l_i \le j \le r_i - k_i$ 的位置 $j$，其上的摩天大楼移动到位置 $j + k_i$；对于所有满足 $r_i - k_i + 1 \le j \le r_i$ 的位置 $j$，其上的摩天大楼移动到位置 $j + k_i - (r_i - l_i + 1)$。 换句话说，你需要将区间 $[l_i, \dots, r_i]$ 内的摩天大楼向右循环移动 $k_i$ 次。

在每次询问后，请帮助 Alexey 判断他是否能完成一次跳跃。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 120\,000$)，表示摩天大楼的数量。 第二行包含 $n$ 个整数 $h_i$ ($1 \le h_i \le n$)，表示摩天大楼的高度。这些高度互不相同。 第三行包含一个整数 $q$ ($1 \le q \le 120\,000$)，表示询问的数量。 接下来 $q$ 行描述询问：第 $i$ 行包含三个正整数 $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le n, 0 \le k_i \le r_i - l_i + 1$)。

输出格式

对于每次询问，单独占一行输出一个单词：“YES”（如果存在合适的摩天大楼可以完成跳跃）或“NO”（否则）。

样例

输入 1

6
2 5 6 1 3 4
1
1 6 5

输出 1

YES

输入 2

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

输出 2

YES
YES
YES
YES

输入 3

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

输出 3

NO
YES

输入 4

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

输出 4

NO
NO
YES

说明

抓钩