중앙값 측정

기상학에서 주로 쓰는 대표값은 중앙값이다. 중앙값의 정의는 힌트에 있다.

1초에 한 번씩 온도를 재는 기계가 있고, 이 기계에 올릴 소프트웨어를 만들려고 한다. 기계에는 작은 디지털 디스플레이가 하나 달려 있다. 디스플레이는 매초 지난 $K$초 동안 측정한 온도의 중앙값을 보여준다.

소프트웨어를 기계에 올리기 전에 컴퓨터에서 먼저 시험해 본다.

$N$초 동안 측정한 온도가 주어질 때, 디스플레이에 표시된 중앙값을 모두 더한 값을 구하는 프로그램을 작성하시오. 즉, $N$개의 수가 주어질 때 길이가 $K$인 연속 부분 수열 $N-K+1$개의 중앙값의 합을 구하면 된다.

첫째 줄에 $N$과 $K$가 주어진다. ($1 \le N \le 250000$, $1 \le K \le 5000$, $K \le N$)

둘째 줄부터 $N$개 줄에 걸쳐 측정한 온도가 한 줄에 하나씩 순서대로 주어진다. 온도는 $0$ 이상 $65535$ 이하의 정수이다.

길이가 $K$인 연속 부분 수열 $N-K+1$개의 중앙값을 모두 더한 값을 출력한다.

수 $K$개의 중앙값은 작은 쪽에서 $\lfloor (K+1)/2 \rfloor$번째에 오는 수이다. 순서는 1번부터 세고, $K$가 홀수일 때 정확히 가운데 값이 나오도록 1을 더한다.

예를 들어 $(1, 2, 6, 5, 4, 3)$의 중앙값은 $3$이고, $(11, 13, 12, 14, 15)$의 중앙값은 $13$이다.