圈小猪

题目背景

piggy 有一块 $L$ 形墙， piggy 想用一些围栏围一长一宽，这样围栏就跟 $L$ 形墙组成了一个矩形！

为什么要这么干？因为 piggy 想养很多头小猪！

题目描述

piggy 很有钱， piggy 的墙是无限长的！piggy 共买来了 $n$ 车围栏。每车围栏长度是 $a_i$ 。但可惜的是对于同一车围栏而言：要么全做成长，要么全做成宽。无聊的 piggy 突发奇想，提出了 $q$ 个问题：

第 $i$ 个问题：只使用 $[l_i,r_i]$ 车的围栏， $[l_i,p]$ 做成长， $(p,r_i]$ 做成宽，跟 $L$ 形墙组成的最大矩形面积是多少呢？

注意：在此题中， 不要求长$\geq$宽 。

输入格式

第一行，整数 $n$ 。

第二行， $n$ 个整数，第 $i$ 个数表示第 $i$ 车的围栏长度 $a_i$ 。

第三行，整数 $q$ 。

接下来的 $q$ 行，每行两个整数表示 $l_i,r_i$ 。

输出格式

输出共 $q$ 行，每行一个整数，表示当前问题的最大矩形面积

输入样例

6
1 5 3 4 2 6
2
1 3
4 6

输出样例

18
36

数据范围

对于 $20\%$ 的数据，$n \leq 5000$，$q = 1$ 。

对于 $50\%$ 的数据，$n \leq 5000$，$q \leq 5000$ 。

对于 $100\%$ 的数据，$n\leq 200000$，$q \leq 200000$ 。

保证所有数据$a_i \leq 10^4$；$r_i-l_i \geq 1$ 。