H. Heavenly Sequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

A sequence $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{good}$$$ if and only if, $$$n=1$$$ $$$\textbf{or}$$$, for some $$$\textbf{non-negative integers}$$$ $$$K$$$ and $$$X$$$, the sequence satisfies: $$$$$$\displaystyle K \cdot \min(b[1],b[2],\dots,b[n]) + X \cdot \max(b[1],b[2],\dots,b[n]) \geq b[n]^2 + \sum_{i=1}^{n-1} b[i] \cdot b[i+1]$$$$$$

A sequence $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{best}$$$ if and only if $$$\textbf{every subsequence}$$$ of $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{good}$$$.

A sequence $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{heavenly}$$$ if and only if $$$\textbf{every permutation}$$$ of $$$b[1],b[2],b[3],\dots,b[n]$$$ is $$$\textbf{best}$$$.

Given the sequence $$$a[1],a[2],a[3],...,a[n]$$$, you have to answer $$$n-1$$$ questions. The $$$i$$$-th question is " Given integers $$$L$$$ and $$$R$$$, what is the minimum $$$\textbf{non-negative integer}$$$ $$$K$$$ that makes the sequence $$$a[1],a[2],a[3],\dots,a[i+1]$$$ $$$\textbf{heavenly}$$$, if you can choose any integer $$$X$$$ from the given range $$$L$$$ to $$$R$$$ ? "

The $$$\textbf{subsequence}$$$ of a sequence can be obtained by erasing some (possibly zero) elements from the array. (not necessary to remove consecutive elements)

Input

The first line contains integer $$$n$$$ $$$(2 \leq n \leq 100,000)$$$ — the length of the sequence

The second line contains $$$a[1], a[2], a[3], \dots, a[n]$$$ $$$(1 \leq a[i] \leq 1,000,000)$$$ — the elements of the sequence

The next $$$n-1$$$ lines contain integers $$$L$$$ and $$$R$$$ $$$(1 \leq L \leq R \leq 1,000,000)$$$ — the range of an integer $$$X$$$ that you can choose in each question

Output

Output $$$n-1$$$ lines, each line contains a single value — the $$$i$$$-th value is the smallest $$$\textbf{non-negative integer}$$$ $$$K$$$ that makes the sequence $$$a[1],a[2],a[3],\dots,a[i+1]$$$ become $$$\textbf{heavenly}$$$, if you can choose any integer $$$X$$$ from the given range $$$L$$$ to $$$R$$$

Examples
Input
4
8 4 5 6
3 4
4 4
20 20
Output
16
23
1
Input
6
12 15 8 9 20 16
9 9
10 14
6 8
40 50
67 67
Output
23
37
59
8
0
Note

For the first question of the first testcase, the sequence is $$$(8,4)$$$ and we can choose $$$X=3$$$ or $$$X=4$$$ and find the smallest non-negative integer $$$K$$$ such that $$$(8,4)$$$ is a $$$\textbf{heavenly}$$$ sequence, which is to make $$$(4)$$$, $$$(8)$$$, $$$(4,8)$$$ and $$$(8,4)$$$ become $$$\textbf{good}$$$. We can choose $$$X=4$$$ and $$$K=16$$$ to satisfy the condition and $$$K=16$$$ is the smallest value of $$$K$$$ that makes $$$(8,4)$$$ become $$$\textbf{heavenly}$$$, so the answer to this question is $$$16$$$.

For the last question of the second question, the smallest integer $$$K$$$ that makes the sequence become $$$\textbf{heavenly}$$$ is a negative integer, but we want the smallest $$$\textbf{non-negative integer}$$$ $$$K$$$, so the answer to this is $$$0$$$.