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 nn integers a1,a2,,an{a_1, a_2, \dots, a_n} and Sumaiya has qq queries.

In a query, Sumaiya will give you 22 integers ll and rr. You have to find a pair of integers kk and pp such that -

  • lk,pr{l \le k, p \le r}

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

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

Input

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

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

The second line contains nn space separated integers a1,a2,,an{a_1, a_2, \dots, a_n} (109ai109){(-10^9 \le a_i \le 10^9)}.

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

The next qq lines contain 22 space separated integers l,r{l, r} (1lrn){(1 \le l \le r \le n)}.

It is guaranteed that sum of nn and sum of qq over all testcases won’t exceed 10510^5 respectively.

Output

For each query, print a pair of integers k,p{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 11: i=12aij=35aj| \sum\limits_{i = 1}^{2} a_i - \sum\limits_{j = 3}^{5} a_j | =217=19=19{= | - 2 - 17 | = |-19| = 19}

Query 22: i=22aij=34aj=38=11=11| \sum\limits_{i = 2}^{2} a_i - \sum\limits_{j = 3}^{4} a_j | = | - 3 - 8 | = |-11| = 11

Query 33: i=33aij=33aj=3(3)=3+3=0| \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.


Discussion

Statistics


59% Solution Ratio

AlfehsaniEarliest, 1M ago

NirjhorFastest, 0.1s

NirjhorLightest, 9.4 MB

sh2018331053Shortest, 1623B

Submit

Login to submit

Editorial

Let's denote prefix sum as Pi=a1+a2+⋯+ai{P_i = a_1 + a_2 + \dots + a_i}Pi​=a1​+a2​+⋯+ai​ and suffix ...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.