K-비둘기 timer 1s memory 512MB

전깃줄 위에 일렬로 N마리의 비둘기가 앉아 있다. 왼쪽에서부터 1, 2, 3, \dots , N번 비둘기이다.

각 비둘기는 오른쪽 또는 왼쪽을 바라보고 있다.

비둘기는 특정한 규칙에 따라 운다.

• i번 비둘기가 왼쪽을 바라보고 있다면, 자신보다 왼쪽에 있으면서 오른쪽을 바라보는 비둘기의 수만큼 운다.

• i번 비둘기가 오른쪽을 바라보고 있다면, 자신보다 오른쪽에 있으면서 왼쪽을 바라보는 비둘기의 수만큼 운다.

정올이는 모든 비둘기가 우는 횟수를 다 더하고 싶은데, 머리가 좋지 않다.

그래서, 연속된 K 마리의 비둘기만 고려할 수 있다.

예를 들어, N=6,~ K=4 이고, 비둘기의 방향이 RLRLLR ( L : 왼쪽, R : 오른쪽) 이라고 하자.

정올이는 연속된 4 개의 비둘기만 고려할 수 있다.

1번째 ~ 4번째 비둘기 : RLRL 이고, 이 때 모든 비둘기가 우는 횟수는 2 + 1 + 1 + 2 = 6 회다.

2번째 ~ 5번째 비둘기 : LRLL 이고, 이 때 모든 비둘기가 우는 횟수는 0 + 2 + 1 + 1 = 4 회다.

3번째 ~ 6번째 비둘기 : RLLR 이고, 이 때 모든 비둘기가 우는 횟수는 2 + 1 + 1 + 0 = 4 회다.

연속된 K 마리 비둘기의 구간은 총 N-K+1 개 존재한다.

각 구간 별로, 모든 비둘기가 우는 횟수를 구하여 출력하자.