• 时间：1s

• 空间：512M

题目描述

对于一个整数数列，如果其先严格递增，然后在某个数的位置开始严格递减，我们称这个数列为单峰数列（严格递增和严格递减的部分均要是非空）。例如 $1,2,2,1$ 不是单峰数列，$1,2,3$不是单峰数列，$1,2,3,1$ 是单峰数列。

给定长度为 $n$ 的整数数列 $a_1,a_2,\cdots,a_n$ ，请你支持 $q$ 次操作：

1. 1 l r x：将 $a_l,a_{l+1},\cdots,a_r$ 的每个数加 $x$。
2. 2 l r：判断 $a_l,a_{l+1},\cdots,a_r$ 的元素是否全都相同。
3. 3 l r：判断 $a_l,a_{l+1},\cdots,a_r$ 是否严格升序排序。当 $l=r$ 时，认为符合严格升序排序。
4. 4 l r：判断 $a_l,a_{l+1},\cdots,a_r$ 是否严格降序排序。当 $l=r$ 时，认为符合严格降序排序。
5. 5 l r：判断 $a_l,a_{l+1},\cdots,a_r$ 是否为单峰数列。保证 $r−l+1\ge 3$。

输入格式

从 peak.in 文件读入数据。

第一行输入包含一个整数 $n$。

第二行输入包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

第三行输入包含一个整数 $q$。

接下来的 $q$ 行，每行描述一个操作，格式见题目描述。

输出格式

输出到 peak.out 文件。

对于每个询问输出一行一个整数，如果查询符合要求输出 1，否则输出 0。

样例

7
3 1 4 1 5 9 2
8
5 1 3
5 4 7
1 3 3 -3
2 2 4
3 3 5
3 4 5
4 1 1
4 1 2

0
1
1
0
1
1
1

样例 2

点击链接 ex_peak2.in 和 ex_peak2.out 下载大样例 2 的输入数据和输出数据。

样例 3

点击链接 ex_peak3.in 和 ex_peak3.out 下载大样例 3 的输入数据和输出数据。

数据范围

对于所有数据，

$3 \leq n \leq 10^5$，

$1 \leq q \leq 2 \times 10^5$，

$0 \leq a_i \leq 10^9$，

对于所有 $1 \leq j \leq q$，$1 \leq op_j \leq 5$，

对于所有 $1 \leq j \leq q$，$1 \leq l_j \leq r_j \leq n$，

对于所有 $1 \leq j \leq q$，$-10^9 \leq x_j \leq 10^9$。

子任务	分数	附加约束条件
$1$	$8$	$n, q \leq 5000$
$2$	$12$	对于所有询问，$r_j - l_j + 1 = 3$
$3$	$13$	只有类型 $2$ 的操作
$4$	$18$	没有类型 $1$ 或类型 $5$ 的操作
$5$	$28$	没有类型 $5$ 的操作
$6$	$21$	无附加限制