Kstar is hosting a party and knows that exactly ~N~ ~(1 \le N \le 500~ ~000)~ people will come, and the order in which they will enter the house. Each person has an integer energy level, ~E_i~ ~(-2000 \le E_i \le 2000)~ which is also known to Kstar.

The synergy level between a pair of people is the product of the two people's energy levels. The combined synergy in the house is equal to the sum of the synergy levels of all distinct pairs of people in the house. Note that Kstar can choose to lock everyone out before anyone comes in.

Kstar wants to start the party after some people have arrived and the energy level is maximized. After which person should Kstar lock the door and stop people from getting in? If there are multiple times where locking the door would yield the maximum synergy, output the first such possible time.

Input Specification

The first line of input will contain ~N~ ~(1 \le N \le 500~ ~000)~, the number of people invited to Kstar's party. The next ~N~ lines will contain an integer ~E_i~ ~(-2000 \le E_i \le 2000)~, the energy level of the ~i^{th}~ person.

Output Specification

Output the least number of people Kstar should let in before closing the door and locking everyone out, in order to maximize total synergy.

Sample Input

4
1
2
8
-5

Sample Output

3

Explanation for Sample Input

After the first person comes in, the combined synergy is ~0~.

After the second person comes in, the combines synergy is ~1 \times 2 = 2~.

After the third person comes in, the combines synergy is ~(1 \times 2)+ (1 \times 8)+ (2 \times 8) = 26~.

After the fourth person comes in, the combines synergy is ~(1 \times 2) + (1 \times 8) + (1 \times -5) + (2 \times 8) + (2 \times -5) + (8 \times -5) = -29~.

Since the combined synergy was the maximum when the third person comes in, Kstar should lock the door after the third person comes in.