Input
4
7 1 2 3
Output
2
Input
2
2 1
Output
1
Input
3
1 1 1
Output
6