시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB35201854.545%

문제

You are given an array of integers $A$ of size $N$ (indexed from $1$ to $N$) where $A_i$ is either $0$, $1$, $2$, or $3$.

A subarray $⟨l, r⟩$ of $A$ is defined as $[A_l , A_{l+1}, \cdots , A_r]$, and its size is $r - l + 1$.

A value $x$ is the only mode of a subarray $⟨l, r⟩$ if and only if $x$ appears strictly more often than other values in subarray $⟨l, r⟩$.

Your task in this problem is to find, for each $x ∈ \{0, 1, 2, 3\}$, the size of the longest subarray of $A$ such that $x$ is the only mode of that subarray, or determine if $x$ cannot be the only mode in any subarray.

입력

Input begins with an integer $N$ ($1 ≤ N ≤ 100\, 000$) representing the size of array $A$. The next line contains $N$ integers $A_i$ ($A_i ∈ \{0, 1, 2, 3\}$).

출력

Output four space-separated integers in a single line. Each integer represents the answer where $x$ is $0$, $1$, $2$, and $3$, respectively. For each value of $x$, if there exists a subarray such that $x$ is the only mode in that subarray, then output the size of the longest subarray; otherwise, output $0$.

예제 입력 1

7
1 2 2 0 3 0 3

예제 출력 1

4 1 5 3
  • The longest subarray such that $0$ is the only mode is $⟨3, 6⟩$ of length $4$, i.e. $[2, 0, 3, 0]$.
  • The longest subarray such that $1$ is the only mode is $⟨1, 1⟩$ of length $1$, i.e. $[1]$.
  • The longest subarray such that $2$ is the only mode is $⟨1, 5⟩$ of length $5$, i.e. $[1, 2, 2, 0, 3]$.
  • The longest subarray such that $3$ is the only mode is $⟨5, 7⟩$ of length $3$, i.e. $[3, 0, 3]$.

예제 입력 2

12
2 0 1 0 2 1 1 0 2 3 3 3

예제 출력 2

4 9 1 9
  • The longest subarray such that $0$ is the only mode is $⟨1, 4⟩$ or $⟨2, 5⟩$.
  • The longest subarray such that $1$ is the only mode is $⟨3, 11⟩$.
  • The longest subarray such that $2$ is the only mode is $⟨1, 1⟩$, $⟨5, 5⟩$, or $⟨9, 9⟩$.
  • The longest subarray such that $3$ is the only mode is $⟨4, 12⟩$.

예제 입력 3

2
0 2

예제 출력 3

1 0 1 0

The longest subarray such that $0$ or $2$ is the only mode contains only a single element by itself; on the other hand, there is no subarray such that $1$ or $3$ is the only mode.

예제 입력 4

12
3 0 2 2 1 0 2 1 3 3 2 3

예제 출력 4

1 5 11 8