有 $n$ 个数 $a_1, a_2, \dots, a_n$，保证两两不同。

有 $q$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_q, r_q]$。对于每个区间，它的权值为

也就是选一个数使得比它大的数个数，乘以这个数本身尽量大。

问所有区间里面，权值最大的是多少。

输入格式

第一行一个整数 $n$。

接下来一行一共 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来一行，一个整数 $q$。

接下来 $q$ 行，每行两个整数 $[l_i, r_i] (1\leq l_i \leq r_i \leq n)$。

输出格式

一个数，表示最大权值区间的权值。

样例输入1

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

样例输出1

9

样例输入输出2

见下发文件。

数据范围

$20\%$, $n\leq 2000$。

另外 $30\%$, 保证数据中的 $a_i$ 和区间 $[l_i, r_i]$ 都是随机生成的。

$100\%$, $1\leq n, q\leq 5\times 10^5, 1\leq a_i\leq 10^9$。