Intermediate.
Put your skills to the test.

Problem summary

Make at least one position equal to its mirrored position using the fewest adjacent swaps. A solution is guaranteed.

Constraints

1≤n≤250000; values lie in [1,65535].

Worked example

Input and output for the worked example discussed below.

6
1 2 3 1 4 5

2

Solution analysis

1. For odd n the middle element matches itself, so the answer is zero. For even n, equal values at positions i<j need their final positions to sum to n+1. Their least required movement is |i+j−(n+1)|.
2. Store each value’s occurrence positions in sorted order. With two pointers, increase the left pointer when their sum is too small and decrease the right pointer when too large. This finds the closest pair sum in linear time per list.
3. The sample’s 1s occupy positions 1 and 4, summing to 5 rather than 7. Move the first 1 right twice to obtain [2,3,1,1,4,5], which qualifies with two swaps.

Why it works

A swap changes the chosen positions’ sum by at most one, giving the lower bound. If the sum is too small, moving the right element right achieves the bound; if too large, move the left element left. The required target stays within [1,n]. Monotone pair sums justify the two-pointer scan.

Watch out. Only one mirrored equality is needed, not a whole palindrome. Use distinct occurrences for even n and 1-based positions.

An independently written complete program with standard headers.

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>>positions(65536);
    for(int i=1;i<=n;i++){
        int value;
        cin>>value;
        positions[value].push_back(i);
    }
    if(n%2==1){
        cout<<0<<'\n';
        return 0;
    }
    int answer=n;
    for(const auto&list:positions){
        int left=0;
        int right=int(list.size())-1;
        while(left<right){
            int sum=list[left]+list[right];
            answer=min(answer,abs(sum-(n+1)));
            // Pair sums change monotonically with either endpoint.
            if(sum<n+1){
                left++;
            }
            else{
                right--;
            }
        }
    }
    cout<<answer<<'\n';
}