You are given an array $A$ of length $N$ containing only the values $1, 2, 3$. We want to find as many ordered triples of indices $(i, j, k)$ as possible that satisfy the following conditions.

For three indices $i, j, k$ in the array ($0 \le i < j < k < N$), the following must hold:

• $A[i]=1, A[j]=2, A[k]=3$, or
• $A[i]=3, A[j]=2, A[k]=1$.

Additionally, each index can be included in at most one triple.

For example, given $A=\{1, 2, 3, 2, 3, 1\}$, one valid answer is $(0, 1, 4)$ and $(2, 3, 5)$. ($A[0]=1, A[1]=2, A[4]=3$, and $A[2]=3, A[3]=2, A[5]=1$.)

Given the array $A$, write a program to find and report the maximum number of such triples.

You need to implement the following function:

• void maximize(vector<int> A)

Here, $A$ is a vector of length $N$ containing only the values $1, 2, 3$. The maximize function must find as many triples $(i, j, k)$ as possible satisfying the conditions, and for each triple found, call the grader-provided function answer(int i, int j, int k) exactly once.

If there are multiple ways to obtain the maximum number of triples, any one of them is acceptable. The order of calls between triples is ignored. That is, in the example above, you may call answer(0, 1, 4) then answer(2, 3, 5), or vice versa.

Implementation Details

You must submit a file named onetwothree.cpp, and only this file. This file must implement the following function:

• void maximize(vector<int> A);

The behavior of this function must be exactly as described above. You may implement and call other helper functions internally. The submitted code must not perform any input/output operations, nor access any other files.

Grader Example

The provided grader will read the input in the following format:

• Line 1: $N$
• Line 2: $N$ integers, each being $1, 2,$ or $3$

The grader will first output the number of times the maximize function calls answer(i, j, k) on the first line, and then for each call to answer(i, j, k), it will output the corresponding $i, j, k$ on the following lines.

Constraints

• $3 \le N \le 15{,}000$

Subtasks

• Subtask 1 (14 points): $N \le 18$
• Subtask 2 (29 points): $N \le 100$
• Subtask 3 (53 points): $N \le 3{,}000$
• Subtask 4 (54 points): No additional constraints beyond the original limits.

Examples

Input

6
1 2 3 2 3 1

Given the input above, depending on the specific behavior of your code, you might get the following execution example:

maximize({1, 2, 3, 2, 3, 1})
answer(0, 1, 4)
answer(2, 3, 5)

The output is:

2
0 1 4
2 3 5