또 다른 Mex 문제

길이가 n인 배열 a와 정수 k가 주어진다. 배열을 길이가 k 이하인 연속된 부분 배열들로 나누어 전체 이익이 최대가 되도록 하라. 부분 배열 하나의 이익은 그 부분 배열의 원소 합에 그 부분 배열의 mex 값을 곱한 것이다. 전체 이익은 모든 부분 배열의 이익을 더한 값이다.

음이 아닌 정수들의 집합에 대한 mex 값은 그 집합에 속하지 않는 가장 작은 음이 아닌 정수이다. 예를 들어 mex(0, 1, 3) = 2이다.

첫 줄에 배열의 길이 n (2 ≤ n ≤ 200 000)과 부분 배열 길이의 상한 k (1 ≤ k ≤ n)이 주어진다.

둘째 줄에는 배열의 원소 n개가 주어진다. i번째 정수는 a_i이며 0 ≤ a_i ≤ n이다.

길이가 k 이하인 부분 배열들로 나누었을 때 얻을 수 있는 이익의 최댓값을 음이 아닌 정수 하나로 출력한다.