arc147 == B - Swap to Sort

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007;

#define got cout<<"YES\n"; return;
#define got0 cout<<"YES\n"; return 0;

#define bhak cout<<"NO\n"; return;
#define bhak0 cout<<"NO\n"; return 0;

#define bas cout<<"\n";

int main() {
    // your code goes here
    vector<ll> odd;

    ll n; cin>>n;
    vector<ll> vec(n);

    map<ll,ll> pos;

    for(ll i=0; i<n; ++i){
        cin>>vec[i];
        ll diff = vec[i] - (i+1);
        pos[vec[i]] = i;

        if(diff==0) continue;
        if(diff%2!=0){
            odd.push_back(vec[i]);
        }
    }

    vector<pair<ll,ll>> ans;

    // Swapping all odd parity difference one's with 1 A operation and other B operation
    for(ll i=0; i<odd.size(); i+=2){
        ll a = odd[i], b = odd[i+1];

        ll start = min(pos[a], pos[b]);
        ll end = max(pos[a], pos[b]);

        while(start!=end-1){
            pos[vec[start]] = start+2;
            pos[vec[start+2]] = start;
            swap(vec[start],vec[start+2]);

            ans.push_back({2, start});
            start +=2;
        }

        pos[vec[start]] = start+1;
        pos[vec[start+1]] = start;
        swap(vec[start], vec[start+1]);
        ans.push_back({1, start});
    }

    // Selection sort with all 'B' operations
    for(ll i=1; i<=n; ++i){
        ll start = min(i-1, pos[i]);
        ll end = max(i-1, pos[i]);

        if(start==end) continue;

        while(start!=end){
            pos[vec[start]] = start+2;
            pos[vec[start+2]] = start;
            swap(vec[start], vec[start+2]);

            ans.push_back({2, start});
            start+=2;
        }
    }


    cout<<ans.size(); bas
    for(auto pr : ans){
        ll a = pr.first, b = pr.second;

        if(a==1){
            cout<<"A ";
        }
        else{
            cout<<"B ";
        }

        cout<<b+1; bas
    }

    return 0;
}