[1] Preface

This problem is a combination of optimization and construction. One can solve it through step-by-step observations organizing the conditions.

[2] Minimizing the number of Operations \(A\)

Let us look at the parity of \(P_i\). Call \(i\) a good index when \(P_i\) and \(i\) have the same parity, and a bad index otherwise. Then, call the number of bad indices the disparity of \(P\), and consider how it changes in the process.

In Operation \(A\), the disparity of \(P\) increases by \(2\), \(0\), or \(-2\), which can be seen from the following case-by-case analysis. Before the operation,

• if both \(i\) and \(i+1\) are good indices: the disparity of \(P\) increases by \(2\).
• if both \(i\) and \(i+1\) are bad indices: the disparity of \(P\) decreases by \(2\).
• if one of \(i\) and \(i+1\) is good and the other is bad: the disparity of \(P\) does not change.

Additionally, in Operation \(B\), the disparity of \(P\) does not change.

From these properties and the fact that the desired state of \(P\) (sorted in ascending order) has a disparity of \(0\), one can see that:

• Operation \(A\) must be performed at least \(\,\frac{1}{2}\times(\) the initial disparity of \(P\) \()\) times.

Note: It can be proved that the disparity of \(P\) is always even, as long as \(P\) is a permutation of \((1,2,\ldots,N)\).

[3] Making the disparity of \(P\) \(0\)

Consider how to make the disparity of \(P\) \(0\) by performing Operation \(A\) exactly \(\,\frac{1}{2}\times(\) the initial disparity of \(P\) \()\) times.

From the case-by-case analysis above, to do with that number of Operations \(A\), one must perform Operation \(A\) only for \(i\) such that both \(i\) and \(i+1\) are bad indices.

This can be easily done when the good and bad indices are in the following arrangement (O and X stand for good and bad indices, respectively):

OOXXOXXO

However, it is a little hard in this case:

So, let us take advantage of the fact that Operation \(B\) may be performed any number of times to make the bad indices gather at an end.

XXXXOOOO

Now, one can perform Operation \(A\) exactly \(\,\frac{1}{2}\times(\) the initial disparity of \(P\) \()\) times to make the disparity of \(P\) \(0\).

Note: One can perform just Operation \(B\) to make the bad indices gather at an end because \(P\) is a permutation of \((1,2,\ldots,N)\) and thus has the same number of even bad indices and odd bad indices.

[4] Sorting \(P\) in ascending order

Now that \(P\) has a disparity of \(0\), \(i\) and \(P_i\) have the same parity for every \(i\). So, by finding \(i\) such that \(P_i>P_{i+2}\) and performing Operation \(B\) for that \(i\), one can sort \(P\) in ascending order.

[5] Analyzing the total number of operations

Finally, let us check whether the total number of operations is at most \(10^5\).

To make the bad indices gather at an end, one has to perform Operation \(B\) at most \(\frac{N}{4}\times\frac{N}{2}\) times.

One has to perform Operation \(A\) at most \(\frac{N}{2}\) times.

To sort \(P\) in ascending order in the end, one has to perform Operation \(B\) at most \((\frac{N}{2})^2\) times.

For \(N=400\), these sum up to \(60200\) operations, well within the limit of \(10^5\).

Sample implementation (C++)

#include <bits/stdc++.h>
using namespace std;
int p[405];
vector<pair<char,int>> ans;
void f(char c,int i){
    ans.emplace_back(c,i+1);
    swap(p[i],p[i+1+c-'A']);
}
int main(){
    int N; cin >> N;
    for(int i=0;i<N;i++) cin >> p[i];
    for(int i=0;i<N;i++) for(int j=0;j<N-2;j++) if(p[j]%2!=p[j+2]%2 && p[j]%2!=j%2) f('B',j);
    for(int i=0;i<N-1;i++)if(p[i]%2!=p[i+1] && p[i]%2==i%2) f('A',i);
    for(int i=0;i<N;i++) for(int j=0;j<N-2;j++) if(p[j]>p[j+2]) f('B',j);
    cout << ans.size() << endl;
    for(auto x:ans) cout << x.first << ' ' << x.second << endl;
}