题目描述

给定一个长度为 $N$ 的序列 $A$，接下来进行 $Q$ 次操作：

• $1\ l\ r(1\leq l\leq r\leq N)$ 表示对 $[l,r]$ 这个区间排序。

• $2\ l\ r(1\leq l\leq r\leq N)$ 查询：如果对这个区间进行冒泡排序，那么交换的相邻两个数的乘积的最大值。

保证 $1$ 操作排序的区间两两不交或包含。

输入格式

输入的第一行将包含一个整数 $N(1≤N≤5\times 10^4)$，表示数组的元素个数。

第二行输入将包含 $N$ 个整数 $(0≤A[i]≤10^9,1≤i≤N)$，即数组的元素。

第三行输入将包含一个整数 $Q(1≤Q≤5\times10^4)$，表示操作次数。

下面的每 $Q$ 行都包含一个题目中描述的询问。

输出格式

$Q$ 行，对每一次询问输出答案。

10
10 9 8 7 6 5 4 3 2 1
11
1 1 2
2 1 2
2 1 3
2 1 10
2 9 10
1 3 4
2 1 4
2 3 4
2 2 3
1 1 4
2 1 4

0
80
80
2
80
0
70
0