The task is really simple: given N exits on a highway which forms a simple cycle, you are supposed to tell the shortest distance between any pair of exits.

Input Specification:

Each input file contains one test case. For each case, the first line contains an integer N (in [3]), followed by N integer distances D​1​​ D​2​​ ⋯ D​N​​, where D​i​​ is the distance between the i-th and the (-st exits, and D​N​​ is between the N-th and the 1st exits. All the numbers in a line are separated by a space. The second line gives a positive integer M (≤), with M lines follow, each contains a pair of exit numbers, provided that the exits are numbered from 1 to N. It is guaranteed that the total round trip distance is no more than 1.

Output Specification:

For each test case, print your results in M lines, each contains the shortest distance between the corresponding given pair of exits.

Sample Input:

5 1 2 4 14 931 32 54 1

Sample Output:

3107

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 int N, M; 5 int main() 6 { 7     cin >> N; 8     int num, a, b; 9     vector
       
        sum(N + 1, 0);10     for (int i = 1; i <= N; ++i)11     {12         cin >> num;13         if (i == N)14             sum[0] = sum[N] + num;15         else16             sum[i + 1] = sum[i] + num;17     }18     cin >> M;19     for (int i = 0; i < M; ++i)20     {21         cin >> a >> b;22         if (a > b)23             swap(a, b);24         int d1 = sum[b] - sum[a];25         int d2 = sum[0] - sum[b] + sum[a] - sum[1];26         cout << (d1 < d2 ? d1 : d2) << endl;27     }28     return 0;29 }