27727번 - 버튼 정렬

문제

길이가 $N$인 수열 $A$와 버튼이 있다.

버튼을 누를 때마다 $A$에서 가장 작은 값을 갖는 원소를 하나 선택하여 1ドル$을 더한다. 그러한 원소가 여러 개라면 그 중 가장 앞에 있는 원소를 선택한다.

입력

첫째 줄에 수열의 길이 $N(1 \leq N \leq 100,000円)$이 주어진다.

둘째 줄에 수열의 원소 $A_i(1 \leq A_i \leq 10^9)$가 공백을 사이에 두고 순서대로 주어진다.

셋째 줄에 버튼을 누른 횟수 $K(1 \leq K \leq 10^{18})$가 주어진다.

주어지는 입력은 모두 정수다.

출력

첫째 줄에 버튼을 $K$번 누르는 동안 $A$가 비내림차순으로 정렬된 횟수를 출력한다.

버튼을 한 번도 누르지 않았을 때 수열이 정렬된 경우는 횟수에 포함하지 않는다.

제한

힌트