고대 기계

안나와 브루노는 고고학자이다. 그들은 IOI 왕국의 유적을 발굴한다. 유적 A에서 안나가 오래된 기계의 배치도를 발견했다. 유적 B에서 브루노가 실제 기계를 발견했다.

이 기계는 $N$개의 장치가 전선에 한 줄로 붙어 있는 구조이다. 장치의 종류는 X, Y, Z 세 가지이다. 장치는 왼쪽부터 0번에서 $N-1$번까지 번호가 매겨져 있다. 장치 $i$의 종류는 $S_i$이며, X, Y, Z 중 하나이다.

기계가 너무 커서 브루노는 장치를 하나씩 제거하기로 했다. 장치들은 전선으로 서로 연결되어 있으므로 제거 순서에 신경 써야 한다.

장치 제거는 다음과 같이 정의한다.

• 장치 $x$, $y$, $z$ ($0 \le x < y < z \le N-1$)가 아직 제거되지 않았고, $S_x$는 X, $S_y$는 Y, $S_z$는 Z이다. 또한 $x < j < y$인 모든 장치 $j$와 $y < k < z$인 모든 장치 $k$가 이미 제거되었다. 이 조건이 모두 성립할 때 장치 $y$를 제거하면 좋은 제거이다.
• 그 밖의 제거는 좋은 제거가 아니다.

브루노는 좋은 제거의 횟수가 최대가 되도록 $N$개의 장치를 모두 제거해야 한다. 다만 세 종류의 장치는 생김새가 비슷해서 브루노는 종류를 구별할 수 없다.

안나는 배치도가 있으므로 각 장치의 종류를 알고 있다. 안나는 송신기로 브루노를 돕는다. 송신기로는 0 또는 1로 이루어진 문자를 보낼 수 있다.

좋은 제거의 횟수가 최대가 되도록 안나의 전략과 브루노의 전략을 구현하는 프로그램을 작성하라. 안나가 보내는 문자 수가 적을수록 높은 점수를 받는다.

샘플 채점기는 표준 입력에서 다음 데이터를 읽는다.

N
S0 S1 ... SN-1

$S_i$와 $S_{i+1}$ ($0 \le i \le N-2$)은 공백으로 구분된다.

프로그램이 정상적으로 종료되면 샘플 채점기는 다음 정보를 표준 출력에 쓴다(설명을 위해 따옴표를 붙였다).

• Wrong Answer [1], [2], [3], [4], [5] 중 하나로 판정되면 Wrong Answer [1]과 같이 그 유형을 쓴다.
• 그 밖의 경우에는 Send 호출 횟수 $L$과 좋은 제거의 횟수 $D$를 Accepted: L D 형식으로 쓴다.

샘플 채점기의 동작은 실제 채점기와 다르다. 샘플 채점기는 Wrong Answer [6] 판정 여부를 확인하지 않는다.

여러 Wrong Answer 유형([1], [2], [3], [4], [5])에 해당하면 샘플 채점기는 그중 하나만 보고한다.

• $3 \le N \le 100,000$.
• $S_i$는 X, Y, Z 중 하나이다 ($0 \le i \le N-1$).