古生物学家们正在寻找恐龙化石！他们已经发现了一排 $n$ 个方形区域，并用 $1$ 到 $n$ 的整数对它们进行了编号。每个方形区域的边长均为 $1$ 米。初步测量显示，在区域 $i$ 中，可能含有恐龙化石的土壤深度为 $a_i$ 米。在该深度之下是坚硬的基岩。所有的数字 $a_i$ 均为互不相同的整数。

科学家们准备了 $q$ 个不同的研究计划。每个计划都包含在编号从 $\ell_j$ 到 $r_j$ 的子区间内建立一个研究站。在选定一个子区间后，他们会从中选择一个区域 $m$ ($\ell_j \le m \le r_j$) 作为主区域。

一个特殊设备将被埋在主区域 $m$ 处，深度为 $a_m$ 米。该设备允许研究人员分析研究站覆盖的所有深度严格大于 $a_m$ 的区域中，深度为 $a_m$ 米的土壤。总共将分析 $a_m \cdot k$ 立方米的土壤，其中 $k$ 是研究站覆盖的区域中（即在 $\ell_j$ 到 $r_j$ 之间，包含端点）深度大于主区域的区域数量。

古生物学家们希望尽可能多地找到恐龙化石，因此他们想要分析尽可能多的土壤。请帮助他们！对于给定的每个计划，求出在选择该子区间并最优地选择主区域后，所能分析的土壤的最大体积。

输入格式

第一行包含一个整数 $n$，表示区域的数量 ($1 \le n \le 10^6$)。

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \dots, a_n$，表示各区域的深度 ($1 \le a_i \le 10^9$)。

第三行包含一个整数 $q$，表示计划的数量 ($1 \le q \le 10^6$)。

接下来的 $q$ 行，每行描述一个计划。第 $j$ 行包含两个整数 $\ell_j$ 和 $r_j$，表示第 $j$ 个计划的子区间端点 ($1 \le \ell_j \le r_j \le n$)。

输出格式

对于每个计划，输出一行，包含一个整数，表示所能分析的土壤的最大体积（单位为立方米）。

样例

输入格式 1

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

输出格式 1

9
12

说明

在第一个计划中，科学家们应该选择第一个区域作为主区域。此时分析的土壤体积为 $3 \cdot 3 = 9$ 立方米（因为 $5, 7, 4$ 均大于 $3$）。 在第二个计划中，科学家们应该选择第三个区域作为主区域。此时分析的土壤体积为 $2 \cdot 6 = 12$ 立方米（因为 $7, 4, 6$ 均大于 $2$）。