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