Input
5 3 1 1 5 5 1 2 4 1 3 3
Output
5
Input
84 5 67 59 41 2 39 56 7 2 15 3 74 18 22 7
Output
42