# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Maximum Distance

By rifatrraazz · Limits 1s, 256 MB

You know it’s hard seeing your favorite person being interested in another one instead of you. At that time, you can do nothing rather than maximize the distance.

Swachha has a sequence of $n$ integers ${a_1, a_2, \dots, a_n}$ and Sumaiya has $q$ queries.

In a query, Sumaiya will give you $2$ integers $l$ and $r$. You have to find a pair of integers $k$ and $p$ such that $-$

• ${l \le k, p \le r}$

• $\Big| \sum\limits_{i = l}^{k} a_i - \sum\limits_{j = p}^{r} a_j \Big|$ is maximum.

Here, $|x|$ denotes the absolute value of $x$.

## Input

The first line of the input contains an integer $t$ ${(1 \le t \le 10^4)}$ denotes the number of testcases.

The first line of each testcase contains an integer $n$ ${(1 \le n \le 10^5)}$.

The second line contains $n$ space separated integers ${a_1, a_2, \dots, a_n}$ ${(-10^9 \le a_i \le 10^9)}$.

The third line contains an integer $q$ ${(1 \le q \le 10^5)}$ denotes the number of queries.

The next $q$ lines contain $2$ space separated integers ${l, r}$ ${(1 \le l \le r \le n)}$.

It is guaranteed that sum of $n$ and sum of $q$ over all testcases won’t exceed $10^5$ respectively.

## Output

For each query, print a pair of integers ${k, p}$ which fulfills the given conditions. If there are multiple possible pairs, you can print any one.

## Sample

InputOutput
1
5
1 -3 2 6 9
5
1 5
2 4
3 3
1 3
2 5

2 3
2 3
3 3
2 3
2 3


Query $1$: $| \sum\limits_{i = 1}^{2} a_i - \sum\limits_{j = 3}^{5} a_j |$ ${= | - 2 - 17 | = |-19| = 19}$

Query $2$: $| \sum\limits_{i = 2}^{2} a_i - \sum\limits_{j = 3}^{4} a_j | = | - 3 - 8 | = |-11| = 11$

Query $3$: $| \sum\limits_{i = 3}^{3} a_i - \sum\limits_{j = 3}^{3} a_j | = | - 3 - (-3) | = |-3 + 3| = 0$

These are the maximum possible distances in the given range.

### Statistics

59% Solution Ratio

AlfehsaniEarliest, 1M ago

NirjhorFastest, 0.1s

NirjhorLightest, 9.4 MB

sh2018331053Shortest, 1623B