Description

在XMU的算法课上，金牌讲师LYH出了一道题来刁难大家
他给了你N个整数，想问问你，在某个区间内，任意两个 位置不同 数字的乘积最小会是多少？
你觉得这种问题太简单了，就diss了一下他，于是他给你增加了难度，使得数字可以改变
现在有两种操作
1.修改操作，将第X个数字变为Y
2.查询操作，查询区间[L,R]中的乘积最小值(L <= x,y <= R 且 Min(Ax*Ay) 且 L<R )

Format

Input

多组测试数据
每组测试数据的第一行包含一个正整数N(1 <= N <= 100000)，表示数字的个数
接下来1行N个整数，为LYH给你的数Xi(-10000 <= Xi <= 10000)
接下来一个整数Q(Q<=100000)表示操作个数
操作如题面所述

Output

针对每个查询操作输出一行一个整数，为所求查询的答案

Sample 1

Input

4
1 2 3 4
5
1 2 -1 
1 3 0
2 1 3
2 3 4
2 1 4

Output

-1
0
-4

Limitation

1s, 128MB for each test case.

Source

Coolxxx