Input

5 
3 -1 2 -3 4 

Output

2

Limitation

1s, 256MiB for each test case.