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