FIICode 2024 Elevi | Minimize Damage

In Legends of the League, Okke is a character that can control time. His most powerful ability is to reverse damage and healing done to him. Of course, he will use it so that the reduction to his health points is minimized.

Damage and healing events are represented as an array $a$ of $n$ integers. Okke will apply the following operation on the array exactly once:

Choose $2$ integers $l$ and $r$ ($1 \le l \le r \le n$) and replace all $a_i$ ($l \le i \le r$) with $-a_i$.

In the end, he wants the sum of the elements of $a$ to be as small as possible.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^5$) – the length of the array $a$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1000 \le a_i \le 1000$).

Output

Print $l$ and $r$ – the indices chosen for the operation.

If there are multiple solutions, print the one that minimizes $r$. If there are multiple solutions that minimize $r$, print the one that maximizes $l$.

Example

stdin

5
3 2 -1 4 -3

stdout

1 4

Notes

After applying the operation for $l = 1$ and $r = 4$, the array becomes $a = \langle -3, -2, 1, -4, -3 \rangle$, having the sum $-11$, which is the smallest possible sum.