z-query

Mr. Little Z is very happy because he has just solved Maximum Sum problem in O(n). Now his brother Mr. Senior Z gives him a harder task.

The task is as follow:
1. Given a set of integers A={a₁,a₂,..,a_N}. (-10000<=a_i<=10000)
2. Given Q queries. Each query consists of 2 numbers, A and B where A<=B<=N.

Mr. Little Z should find the maximum substring from a_A to a_B and also find the number of elements of that substring. He needs your help to solve this task.

OutputTo the standard output write two numbers that are the maximum substring and the number of elements of that substring.

Notes: if there are more than 2 maximum substring with different number of elements, take the one with bigger number of elements of that substring.

Input 1:
3
-1 -2 -3
1
1 1
Output 1:
-1 1

Input 2:
8
1 2 -1 4 9 8 -1 2
4
1 3
1 4
2 5
7 8
Output 2:
3 2
6 4
14 4
2 1

Input 3:
3
0 0 0
1
1 3
Output 3:
0 3

Explanation of Input 2:
[b]Set:
1 2 -1 4 9 8 -1 2

Query: 1 3(bold)
1 2 -1 4 9 8 -1 2
(1 2) -1
the maximal substring = 1+2=3
the number of elements in substring=2

Query: 1 4
1 2 -1 4 9 8 -1 2
(1 2 -1 4)
the maximal substring= 1+2+(-1)+4=6
the number of elements in substring=4

Query: 2 5
1 2 -1 4 9 8 -1 2
(2 -1 4 9)
the maximal substring = 2+(-1)+4+9
the number of elements in substring=4

Query: 7 8
1 2 -1 4 9 8 -1 2
-1 (2)
the maximal substring= 2
the number of elements in substring=1