6701: 单峰数列

内存限制:256 MB 时间限制:2 S
题面:Markdown 评测方式:文本比较 上传者:
提交:6 通过:4

题目描述

对于一个整数数列,如果其先严格递增,然后在某一点后严格递减,我们称这个数列为单峰数列(严格递增和严格递减的部分均要是**非空**)。

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

1. `1 l r x`:将 $a_l,a_{l+1},\dots,a_r$ 的每个数加 $x$。

2. `2 l r`:判断 $a_l,a_{l+1},\dots,a_r$ 的元素是否全都相同。

3. `3 l r`:判断 $a_l,a_{l+1},\dots,a_r$ 是否严格升序排序。当 $l = r$ 时,认为符合严格升序排序。

4. `4 l r`:判断 $a_l,a_{l+1},\dots,a_r$ 是否严格降序排序。当 $l = r$ 时,认为符合严格降序排序。

5. `5 l r`:判断 $a_l,a_{l+1},\dots,a_r$ 是否为单峰数列。保证 $r - l + 1 \geq 3$。
 

输入格式

第一行输入包含一个整数 $n\ (3 \leq n \leq 10^5)$。

第二行输入包含 $n$ 个整数 $a_1, a_2, \dots, a_n\ (0 \leq a_i \leq 10^9)$。

第三行输入包含一个整数 $q\ (1 \leq q \leq 2 \times 10^5)$。

接下来的 $q$ 行,每行描述一个操作,格式见题目描述。对于第一类操作,保证 $-10^9 \leq x \leq 10^9$。

输出格式

对于每个询问输出一行一个整数,如果查询符合要求输出 `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