丁真的小马朋友们
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

丁真养了一大群小马，今天是理塘一年一度的收马日，丁真需要计算小马们的价格，可是丁真不会数数，所以他会跟你说 K 句话，可能是将小马单价 a_i 修改成 x_i，也可能是询问编号从 L_i 到 R_i 的小马们最大的价格。

对编号从 L 到 R 的小马们的价格的计算方式如下:

V_{LR} = max \{ a_l,a_{l+1},...,a_{r}\} \times min\{a_l,a_{l+1},...,a_{r}\} ( L \leq l \lt r \leq R )。

(请注意 l 不一定等于 L ，且 l 必须小于 r ，即在 L 到 R 中选取某段 l 到 r 的长度大于 1 的区间)

正当你准备用一种朴素的 O(K \times n^3) 算法来解决时，丁真觉得你的办法不够聪明：“都什么年代了，还在用传统办法做，我有一个绝妙的 O(K \times log_2n) 办法，可惜我忙着赚钱而无法告诉你。”

输入描述:

第一行输入一个整数 n ，表示序列的长度。

第二行输入一个长度为 n 的序列 \{a_i\}，代表每匹马的价格。

第三行输入一个整数 K ，表示有 K 次对话。

接下来 K 行，每行三个整数，第一个整数是 OP 。

如果 OP=1 ，则接下来两个整数是 i 和 x_i ,表示将 a_i 修改成 x_i 。

如果 OP=2 ，则接下来两个整数是 L_i 和 R_i ，表示询问编号从 L_i 到 R_i 的小马们最大的价格。


输出描述:

对于每次 OP=2 的询问进行回答，每行一个整数，表示编号从 L_i 到 R_i 的小马们最大的价格。

示例1

输入

复制 
6
2 8 9 1 11 3
5
2 1 5
2 1 3
1 2 1
2 1 3
2 1 5

输出

复制 
72
72
9
11

说明

第一次对话，询问得到的最大价格的区间是l=2,r=3,即[8,9]，价格为8 \times 9=72。

第二次对话，询问得到的最大价格的区间是l=2,r=3,即[8,9]，价格为8 \times 9=72。

第三次对话，修改后序列为[2,1,9,1,11,3]。

第四次对话，询问得到的最大价格的区间是l=2,r=3,即[1,9]，价格为1 \times 9=9。

第五次对话，询问得到的最大价格的区间是l=4,r=5,即[1,11]，价格为1 \times 11=11。

备注:

2 \leq n,k \leq 2\times10^5 ,1 \leq a_i,x_i \leq 10^9 ,1 \leq i \leq n,1\leq L_i \lt R_i \leq n。