Maximize Valid Triplets

You are given an array A of length \(N\) consisting only of the numbers 1, 2, and 3. Your task is to select as many disjoint triplets \((i, j, k)\) as possible (each index may be used at most once) such that:

• \(0 \le i < j < k < N\), and
• either \(A[i] = 1,\; A[j] = 2,\; A[k] = 3\) (pattern 1-2-3) or \(A[i] = 3,\; A[j] = 2,\; A[k] = 1\) (pattern 3-2-1).

For example, if \(A = \{1,2,3,2,3,1\}\) then one optimal selection is:

• \((0,1,4)\), where \(A[0]=1,\; A[1]=2,\; A[4]=3\), and
• \((2,3,5)\), where \(A[2]=3,\; A[3]=2,\; A[5]=1\).

You must implement a function with the following signature:

void maximize(vector<int> A);

Inside your function, for each triplet you select you should call the grader’s function answer(int i, int j, int k) exactly once. The order in which you output the triplets does not matter. If there are multiple ways to achieve the maximum number of valid triplets, output any one of them.

Note: Two triplets are disjoint if they do not share any index. The challenge is to maximize the total number of disjoint valid triplets.

inputFormat

The input is provided as a parameter to the function maximize:

• A vector A of length \(N\) where each element is either 1, 2, or 3.

outputFormat

Your function should not return any value. Instead, for every valid triplet selected, output the answer by calling grader.answer(i, j, k) exactly once. The triplets need to be disjoint and their order does not matter.

sample

6
1 2 3 2 3 1

Possible grader.answer calls (order does not matter):
answer(0,1,4)
answer(2,3,5)