Migrated from Lutece 2834 Rapport Test

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Kanade, Yuzuru, and Yuri are playing Overcooked! 2, a multi-player game that needs much rapport between players. But they seem to have no rapport at all. So they decide to have a test.

There is an array $a$ consisting of $n$ integers. The test will be performed on this array for $m$ times. Yuri, Kanade, and Yuzuru will take an integer away from one subarray of $a$ by turns. After an integer is taken away, it will disappear from the array. The only requirement is that the largest integer taken out is strictly less than the sum of the other two. The score for this time is the sum of the three integers they take away. After calculating the score, they will put back these integers to their original positions. If the requirement can't be satisfied, the score is $-1$.

Kanade would like to know the maximum scores they can reach each time.

Input

The first line contains one integer $n\ (3\le n\le 10^5)$ --- indicating the size of array $a$.

The second line contains $n$ integers, indicating the array $a$. The $i$-th integer indicates $a_i\ (0\le a_i\le 10^9)$.

The third line contains one integer $m\ (1\le m\le 10^5)$ --- indicating the number of tests.

For the next $m$ lines, each line contains two integers $l,r\ (1\le l\le r\le n)$, indicating the subarray they take integers away from is $a_l,a_{l+1},\ldots ,a_r$.

Output

Output $m$ lines, the $i$-th line contains the maximum score they can reach in the $i$-th test.

Samples

6
1 9 1 9 8 1
2
4 6
1 6

-1
26

Resources

The 18th UESTC Programming Contest Preliminary