Input
3 5 1 2 1 2 3 2 3 3 3 2 1 4 2 2 5
Output
4