You are a game developer at Team Berry and you have released a wildly successful indie game called Solid Knight. It is so successful that people are skipping classes and even AUCPL competitions to play it! However, many players are complaining that certain sections of the game are too hard, so you want to tune the game balance by separating the game stages into two distinct chapters.

Each stage in the game has a different difficulty value, detailing how hard it is to complete. You want to split the given game stages into two contiguous chapters at some point such that the balance ratio of the chapters is as close to ~1~ as possible. The balance ratio of a given split is defined as follows: given ~n~ game stages with elements ~a_i~ (1-indexed) and a split index ~k\ (1 \leq k < n)~, the game balance is

$$\displaystyle R = \frac{\text{average difficulty of Chapter 1}}{\text{average difficulty of Chapter 2}} = \frac{\frac{1}{k}\sum_{i=1}^{k} a_i}{\frac{1}{n-k}\sum_{i=k+1}^{n} a_i} $$

We want to find ~k~ such that ~|R-1|~ is minimised. If multiple ~k~ values would have the same best split, output the lowest one.

Input

The first line contains a single integer ~n\ (2 \leq n \leq 10^5)~, the number of stages in the game.

The next line contains ~n~ space-separated integers ~a_i\ (1 \leq a_i \leq 10^6)~, the difficulties of each stage.

Output

Output the ~1~-based index ~k~ of the position where we should split the game chapters in order to make the above defined balance ratio as close to ~1~ as possible. Note that the chapter one includes game ~k~ while chapter two doesn't. In the case of ties, i.e. multiple splits have the same minimal absolute difference, output the earlier index.

Example

Input 1

5
2 2 6 6 6

Output 1

4

We will enumerate all possibilities to find the optimal split:

• ~k=1~: Average of chapter one is ~2~, average of chapter two is ~\frac{20}{4}=5~. The balance ratio is ~\frac{2}{5}~.
• ~k=2~: Average of chapter one is ~2~, average of chapter two is ~6~. The balance ratio is ~\frac{1}{3}~.
• ~k=3~: Average of chapter one is ~\frac{10}{3}~, average of chapter two is ~6~. The balance ratio is ~\frac{5}{9}~.
• ~k=4~: Average of chapter one is ~\frac{16}{4}=4~, average of chapter two is ~6~. The balance ratio is ~\frac{2}{3}~.

Thus, the split at ~k=4~ is optimal as ~\frac{2}{3}~ is closest to one. We can illustrate this by finding the absolute difference with one and then converting to a common denominator:

• ~\left|\frac{2}{5}-1\right|=\frac{3}{5}=\frac{27}{45}~
• ~\left|\frac{1}{3}-1\right|=\frac{2}{3}=\frac{30}{45}~
• ~\left|\frac{5}{9}-1\right|=\frac{4}{9}=\frac{36}{45}~
• ~\left|\frac{2}{3}-1\right|=\frac{1}{3}=\frac{15}{45}~

The final one is the lowest difference, hence why ~k=4~ is the output.

Input 2

7
5 3 1 2 3 6 1

Output 2

3

We can perfectly split into two sections with equal averages.