题目描述

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

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

1. 1 l r x：将 $a_l,a_{l+1},…,a_r$ 的每个数加 $x$。

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

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

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

5. 5 l r：判断 $a_l,a_{l+1},…,a_r$ 是否为单峰数列。保证 $r−l+1≥3$。

输入格式

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

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

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

接下来的 $q$ 行，每行描述一个操作，格式见题目描述。对于第一类操作，保证 $−10^9≤x≤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