Sometimes you must fall in order to rise but I seemed to be already dead. The abyss behind me was getting the bigger the further I was moving away of it. I turned around, looked into it and saw myself at the very bottom of it. And at that moment I realized I was still alive.
I was sleeping, and the shadows of the past took advantage of it to take their shapes. I saw my wife and my daughters. They were dead. I also saw the sequence a1, ..., an of n integers. I had to find some consecutive elements in this sequence such that their sum was equal to zero. It was a matter of life and death. I had no time so I had to find the minimal possible number of such elements.
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the length of the sequence from the dream.
The second line contains n integers separated by spaces: ai ( - 109 ≤ ai ≤ 109) — the sequence itself.
Output two integers separated by a space: the 1-based position in the sequence, starting from which the consecutive elements must be taken, and how many elements must be taken. If there are several possible answers, output any of them. If it's impossible to find the elements satisfying the statement, output a single integer –1 instead.
## Input
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the length of the sequence from the dream.The second line contains n integers separated by spaces: ai ( - 109 ≤ ai ≤ 109) — the sequence itself.
## Output
Output two integers separated by a space: the 1-based position in the sequence, starting from which the consecutive elements must be taken, and how many elements must be taken. If there are several possible answers, output any of them. If it's impossible to find the elements satisfying the statement, output a single integer –1 instead.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ N \in \mathbb{Z} $ be the number of nodes, with node 1 as the root.
- Let $ E = \{ (p_i, c_i) \mid i \in \{2, \dots, N\} \} $ be the set of edges, where $ p_i $ is the parent of node $ i $, and $ c_i \in \mathbb{R}_{\geq 0} $ is the ice amount on edge $ (p_i, i) $.
- Let $ \mathcal{T} = (V, E) $ be the tree with $ V = \{1, 2, \dots, N\} $.
- Let $ L \subseteq V $ be the set of leaves: $ L = \{ v \in V \mid \text{deg}^+(v) = 0 \} $, where $ \text{deg}^+(v) $ is the out-degree (number of children).
**Constraints**
1. $ 1 \leq T \leq 100 $
2. $ 2 \leq N \leq 100{,}000 $
3. $ 1 \leq p_i \leq N $, $ 0 \leq c_i \leq 100{,}000 $ for all edges
4. $ 1 \leq Q \leq 100{,}000 $ queries per test case
5. Each query time $ t_q \in [0, 10^{12}] $
**Melting Dynamics**
- Water originates at node 1 at time 0.
- When water first reaches a node $ u $, it begins melting all edges $ (u, v) $ to its children at rate $ r = 1 $ unit/second.
- Once edge $ (u, v) $ is fully melted (at time $ t_{uv} = \text{arrival time at } u + c_{uv} $), the melting rate of all *other* edges from $ u $ drops to $ r = 0.5 $, and the edges from $ v $ begin melting at rate $ r = 1 $.
**Objective**
For each query time $ t_q $, compute:
$$
\left| \left\{ \ell \in L \mid \text{water reaches } \ell \text{ at or before time } t_q \right\} \right|
$$
where "water reaches $ \ell $" means the entire path from root to $ \ell $ has been melted.