Description

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 $\langle l, r \rangle$ 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 $\langle l, r \rangle$ if and only if $x$ appears strictly more often than other values in subarray $\langle l, r \rangle$.

Your task in this problem is to find, for each $x \in \{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 Format

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

Output Format

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$.

7
1 2 2 0 3 0 3

4 1 5 3

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

4 9 1 9

2
0 2

1 0 1 0

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

1 5 11 8

Hint

Explanation for the sample input/output #1

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

Explanation for the sample input/output #2

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

Explanation for the sample input/output #3

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.