32347번 - 시간을 돌리고 싶어

문제

종강한지 벌써 $N$일차... 곧 있으면 개강이다. 지금 돌이켜 생각해보면 종강 이후에 열심히 살지 않은게 너무나 후회된다. 그래서 나는 타임머신을 미리 개발해두었다. 하지만 타임머신에는 까다로운 조건이 붙게 되었다.

• 타임머신은 최대 $K$번 사용할 수 있다.
• 타임머신을 사용하면 $T$일 전으로 갈 수 있다. 단, 현재로부터 $T$일 전이 1ドル$일 이전이라면 1ドル$일로 가게 된다.
• $i$일에 타임머신을 사용하기 위해서는 $i$일에 타임머신에 전원이 공급되고 있어야 한다.
• 타임머신을 타고 과거로 간 뒤, 과거에서 시간을 보내는 것도 가능하다.

전력 소모가 너무 커서 타임머신을 종종 꺼둔 것을 후회하면서, 어떻게 해야 $T$를 최소화하며 1ドル$일로 돌아갈 수 있는지 계산해보려고 한다. 1ドル$일로 돌아가기 위한 $T$의 최솟값을 구해보자!

입력

첫째 줄에 현재 일차인 정수 $N,ドル 타임머신의 최대 사용 횟수 $K$이 주어진다. $(2 \leq K < N \leq 200,000円)$

둘째 줄에 타임머신의 전원 공급 정보를 담은 수열 $A$가 공백으로 구분되어 주어진다. $(A_i \in \{0, 1\}; A_n = 1)$ $i$일에 타임머신에 전원이 공급되고 있었다면 $A_i = 1,ドル 그렇지 않다면 0ドル$이다.

출력

첫째 줄에 1ドル$일로 돌아가기 위한 $T$의 최솟값을 출력한다.

제한

힌트