시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB0000.000%

문제

In this problem, we consider three types of integer sequences: the Good, the Great, and the Superb.

A sequence is considered as Superb if it contains at least 3 elements, and all the elements are of the same value. For example, (1, 1, 1), (4, 4, 4, 4), and (9, 9, 9, 9, 9, 9) are Superb sequences.

A sequence is considered as Great if it contains at least 3 elements, and the difference between any successive elements is at most 1. By definition, all Superb sequences are also Great sequences. For example, (1, 2, 3, 4), (4, 4, 3, 2, 3), (5, 5, 5) are Great sequences.

A sequence is considered as Good if it is constructed from concatenation of any Great or Superb sequences. By definition, all Great or Superb sequences are also Good sequences. For example,

  • (2, 2, 3, 6, 6, 6) from (2, 2, 3) concatenated with (6, 6, 6).
  • (5, 5, 5, 5) from (5, 5, 5, 5).
  • (4, 3, 4, 7, 7, 8, 9, 2, 1, 0) from (4, 3, 4) concatenated with (7, 7, 8, 9) and (2, 1, 0).

You are given a sequence of N integers S, your task is to find three integers: a, b, and c, which represent the minimum number of elements you need to modify such that S become a Good sequence, a Great sequence, and a Superb sequence, respectively.

입력

Input begins with an integer N (3 ≤ N ≤ 100000) representing the number of integers in S. The next line contains N integers: Si (0 ≤ Si ≤ 9) representing the given integer sequences.

출력

Output in a line three integers a b c (each separated by a single space) representing the minimum number of elements you need to modify from S such that it becomes a Good sequence, a Great sequence, and a Superb sequence, respectively.

예제 입력 1

4
1 2 3 4

예제 출력 1

0 0 3

예제 입력 2

7
2 8 0 2 3 7 4

예제 출력 2

2 3 5

Following are some example sequences (the underlined elements are modified):

  • 2 8 0 2 3 7 4 : Original sequence.
  • 2 1 0 2 3 4 4 : Good sequence (2 modifications).
  • 2 2 2 2 3 4 4 : Great sequence (3 modifications).
  • 2 2 2 2 2 2 2 : Superb sequence (5 modifications).

예제 입력 3

7
1 2 4 4 6 7 8

예제 출력 3

1 3 5

Following are some example sequences (the underlined elements are modified):

  • 1 2 4 4 6 7 8 : Original sequence.
  • 1 2 3 4 6 7 8 : Good sequence (1 modification).
  • 2 3 4 5 6 7 8 : Great sequence (3 modifications).
  • 4 4 4 4 4 4 4 : Superb sequence (5 modifications).