403159: GYM101055 B Pharaoh's Bank

Not many people know, but it was in Ancient Egypt that the first banks were created. The main bank was the pharaoh's, who decided, from time to time, to seize some accounts.

Given N, the number of accounts in the Pharaoh's Bank (that was its name), each account had an amount of money in menes (old Egyptian coin) that could be positive or negative (negative means they owe that quantity to the bank), that is, each account can be represented by an integer a_i.

The pharaoh could only take accounts from a continuous segment, that is, he can take all accounts i, i + 1, ..., j, for some i ≤ j. So the pharaoh is interested in knowing, for some intervals [L, R] (corresponding to accounts a_L, a_L + 1, ..., a_R), what is the continuous subsegment of maximum sum, that is, which segment he can seize to get the greatest amount of money.

This was explained to the clients as being an offering to Amon-Ahcid, the Egyptian god of money. Doing constant offerings, the god would be pleased and allow the economic system to prosper. This, surprisingly, lasted for more than 500 years, until in one of these seizes the clients rebelled, took the palace, and killed the pharaoh. The bank was sacked and the system collapsed. Banks were only heard of again centuries later.

Your task is, given a record of the accounts and some queries, answer for each one the subsegment of maximum sum, and its size.

The first line has a single integer N, the number of accounts. The second line has N integers a₁, ..., a_N, the balance in each account.

The third line has an integer Q the number of queries, and each of the next Q lines has two integers L and R, the interval that should be queried.

Limits

• 1 ≤ N, Q ≤ 10⁵
• |a_i| ≤ 10⁴
• 1 ≤ L ≤ R ≤ N

Print two integers, the maximum subsegment sum and the size of that subsegment. If there are multiple possible sizes, print the greatest.

3
-1 -2 -3
1
1 1

-1 1

8
1 2 -1 4 9 8 -1 2
4
1 3
1 4
2 5
7 8

3 2
6 4
14 4
2 1

3
0 0 0
1
1 3

0 3