Ancient Machine

Anna and Bruno are archaeologists. They excavate the ruins of the IOI Kingdom. At ruin A, Anna discovered the layout of an old machine. At ruin B, Bruno discovered the actual machine.

The machine consists of $N$ devices attached to an electric wire in a row. There are three device types, X, Y, and Z. The devices are numbered from 0 to $N-1$ from the left. The type of device $i$ is $S_i$, which is X, Y, or Z.

The machine is too big, so Bruno decided to remove the devices one by one. The devices interact through the electric wire, so he must be careful about the removal order.

A removal is defined as follows.

• Suppose devices $x$, $y$, $z$ ($0 \le x < y < z \le N-1$) are not yet removed, $S_x$ is X, $S_y$ is Y, and $S_z$ is Z. Also suppose every device $j$ with $x < j < y$ is already removed, and every device $k$ with $y < k < z$ is already removed. If all these conditions hold and device $y$ is removed, this is called a good removal.
• Any other removal is not a good removal.

Bruno must remove all $N$ devices so that the number of good removals is as large as possible. However, the three device types look alike, so Bruno cannot tell the types apart.

Anna knows the type of each device because she has the layout. She uses a transmitter to help Bruno. Through the transmitter, she can send a sequence of characters, each either 0 or 1.

Write a program that implements Anna's strategy and Bruno's strategy so that the number of good removals is maximized. Anna gets a higher score the fewer characters she sends.

The sample grader reads the following data from standard input.

N
S0 S1 ... SN-1

$S_i$ and $S_{i+1}$ ($0 \le i \le N-2$) are separated by a space.

When the program terminates successfully, the sample grader writes the following information to standard output (quotes are added for clarity).

• If your program is judged as any one of Wrong Answer [1], [2], [3], [4], or [5], it writes its type as Wrong Answer [1].
• Otherwise, it writes the number $L$ of calls to Send and the number $D$ of good removals as Accepted: L D.

The sample grader behaves differently from the actual grader. It does not check whether your program is judged as Wrong Answer [6].

If your program falls under several of Wrong Answer [1], [2], [3], [4], or [5], the sample grader reports only one of them.

• $3 \le N \le 100,000$.
• $S_i$ is one of X, Y, or Z ($0 \le i \le N-1$).