FIICode 2024 Elevi | School Championship

The 1T academy wants to organize the school Legends of the League championship. Rekaf is in charge of making teams in his class, but he is too busy practicing his favourite character Zeb, so he asks you to help.

There are $n$ students in Rekaf's class, each having a power level $a_i$. Because you are also pretty busy, you chose a simple method to form teams:

1. Choose $3$ integers $i$, $j$, and $k$ ($1 \le i < j < k < n$).
2. Create $4$ teams:
   • $A$ contains students $1, 2, \ldots, i$.
   • $B$ contains students $i + 1, i + 2, \ldots, j$.
   • $C$ contains students $j + 1, j + 2, \ldots, k$.
   • $D$ contains students $k + 1, k + 2, \ldots, n$.

Let $\mathrm{sum}(X)$ be the sum of power levels of students in team $X$.

Because you want the teams to be somewhat balanced, you will choose $i$, $j$, and $k$ such that $\mathrm{sum}(A) = \mathrm{sum}(D)$ and $\mathrm{sum}(B) = \mathrm{sum}(C)$.

Input

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

Output

Print $i$, $j$, and $k$.

If there are multiple solutions, print the lexicographically smallest one. The triplet $(a, b, c)$ is smaller than $(x, y, z)$ if any of the following holds true:

• $a < x$;
• $a = x$ and $b < y$;
• $a = x$ and $b = y$ and $c < z$.

For example, $(1, 2, 3) < (3, 4, 5)$, $(3, 4, 7) < (3, 5, 6)$, and $(1, 2, 3) < (1, 2, 4)$.

If there are no solutions, print $-1$.

Example 1

stdin

8
1 1 2 1 2 4 1 2

stdout

2 5 7

Example 2

stdin

5
1 1 1 1 1

stdout

-1

Notes

In the first example, the teams are $A = \langle 1, 1 \rangle$, $B = \langle 2, 1, 2 \rangle$, $C = \langle 4, 1 \rangle$, and $D = \langle 2 \rangle$. Therefore, $\mathrm{sum}(A) = \mathrm{sum}(D) = 2$ and $\mathrm{sum}(B) = \mathrm{sum}(C) = 5$.