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)
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 $$$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$$$
48 4 5 63 44 420 20
16 23 1
612 15 8 9 20 169 910 146 840 5067 67
23 37 59 8 0
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$$$.
