Return to Question

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. Given \$M\$ queries, your program must output the results of these queries.

Input

• The first line of the input file contains the integer \$N\$.
• In the second line, \$N\$ numbers follow.
• The third line contains the integer \$M\$.
• \$M\$ lines follow, where line \$i\$ contains 2 numbers \$x_i\$ and \$y_i\$.

Output

Your program should output the results of the \$M\$ queries, one query per line.

Example

Input:

3 -1 2 3

1 1 2

Output:

2

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. Given \$M\$ queries, your program must output the results of these queries.

Input

• The first line of the input file contains the integer \$N\$.
• In the second line, \$N\$ numbers follow.
• The third line contains the integer \$M\$.
• \$M\$ lines follow, where line \$i\$ contains 2 numbers \$x_i\$ and \$y_i\$.

Output

Your program should output the results of the \$M\$ queries, one query per line.

Example

Input:

3

-1 2 3

1 1 2

Output:

2

The link to the problem is here.

The problem is presented here as follows:

You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. Given \$M\$ queries, your program must output the results of these queries.

Input

• The first line of the input file contains the integer \$N\$.
• In the second line, \$N\$ numbers follow.
• The third line contains the integer \$M\$.
• \$M\$ lines follow, where line \$i\$ contains 2 numbers \$x_i\$ and \$y_i\$.

Output

Your program should output the results of the \$M\$ queries, one query per line.

Example

Input:

3 -1 2 3

1 1 2

Output:

2