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

*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$.

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.

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.

Input | Output |
---|---|

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. |

59% Solution Ratio

AlfehsaniEarliest,

NirjhorFastest, 0.1s

NirjhorLightest, 9.4 MB

sh2018331053Shortest, 1623B

Login to submit

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 ...

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