Good, Great, Superb

시간 제한1초메모리 제한512 MB

요약

숫자열이 주어질 때, Superb(모든 원소가 같은 수), Great(인접한 차이가 1 이하), Good(Great 또는 Superb 블록의 연결)이 되도록 바꿔야 하는 원소 수의 최솟값을 각각 구한다.

문제

이 문제에서는 세 가지 종류의 정수 수열을 다룬다. Good, Great, Superb이다.

수열이 Superb라는 것은 원소가 3개 이상이고 모든 원소의 값이 같다는 뜻이다. 예를 들어 (1, 1, 1), (4, 4, 4, 4), (9, 9, 9, 9, 9, 9)는 Superb 수열이다.

수열이 Great이라는 것은 원소가 3개 이상이고 이웃한 두 원소의 차가 1 이하라는 뜻이다. 정의에 따라 모든 Superb 수열은 Great 수열이기도 하다. 예를 들어 (1, 2, 3, 4), (4, 4, 3, 2, 3), (5, 5, 5)는 Great 수열이다.

수열이 Good이라는 것은 임의의 Great 수열 또는 Superb 수열을 이어 붙여서 만들 수 있다는 뜻이다. 정의에 따라 모든 Great 수열과 Superb 수열은 Good 수열이기도 하다. 예를 들어,

(2, 2, 3, 6, 6, 6)은 (2, 2, 3) 뒤에 (6, 6, 6)을 이어 붙인 것이다.
(5, 5, 5, 5)는 (5, 5, 5, 5) 하나로 이루어진 것이다.
(4, 3, 4, 7, 7, 8, 9, 2, 1, 0)은 (4, 3, 4), (7, 7, 8, 9), (2, 1, 0)을 차례로 이어 붙인 것이다.

N개의 정수로 이루어진 수열 S가 주어진다. S를 각각 Good 수열, Great 수열, Superb 수열로 만들기 위해 값을 바꿔야 하는 원소 개수의 최솟값을 나타내는 세 정수 a, b, c를 구하시오.

첫 줄에 S의 길이를 나타내는 정수 N (3 ≤ N ≤ 100000)이 주어진다. 다음 줄에 S를 이루는 N개의 정수 Si (0 ≤ Si ≤ 9)가 주어진다.

S를 각각 Good 수열, Great 수열, Superb 수열로 만들기 위해 값을 바꿔야 하는 원소 개수의 최솟값 a, b, c를 공백 하나를 사이에 두고 한 줄에 출력한다.