<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

325. Palindrome
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



You are given a word. You can perform the only operation to this word: swap two adjacent letters. Your task is to make a palindrome from the original word using the minimal number of swaps. The palindrome is a word which is spelled the same way when reading from left to right and from right to left.

For example, the word "ABBYY" can be transformed to the palindrome "YBABY" using 4 swaps:

ABBYY BABYY BAYBY BYABY YBABY

Input
The only line of the input contains the given word. The word is written using capital Latin letters. The length of the word is no less than one and no more than 1000000 letters.

Output
Write the minimum possible number of swaps required to get a palindrome from the given word to the output. If it is impossible to get a palindrome, write -1 to the output.

Example(s)
sample input
sample output
MISSISSIPPI
13

<|response|>
## 1) Abridged problem statement (concise)

Given a string `s` (1 ≤ |s| ≤ 1,000,000) consisting of uppercase Latin letters, you may swap **adjacent** characters. Compute the **minimum** number of adjacent swaps required to transform `s` into **some palindrome**. If no palindrome can be formed from the multiset of letters, output `-1`.

---

## 2) Key observations

1. **Feasibility condition (necessary and sufficient)**
   A palindrome can be formed iff the number of characters with **odd** frequency equals `n % 2`:
   - `n` even → `0` odd counts
   - `n` odd → `1` odd count (the center character)

2. **Adjacent swaps ↔ inversion count**
   If we choose a target arrangement and describe it as an array `p`:
   - `p[final_pos] = original_index` (which original character goes to that final position)

   Then the minimal number of adjacent swaps to realize that target equals the number of **inversions** in `p`:
   \[
   \#\text{swaps} = \#\{(i<j) \mid p[i] > p[j]\}
   \]
   Reason: adjacent swaps are exactly the operations that sort a permutation; each swap changes inversion count by 1.

3. **Optimal pairing of equal letters**
   For each letter whose occurrences are at indices:
   \[
   i_1 < i_2 < \dots < i_k
   \]
   In an optimal palindrome, you should pair them as:
   - `(i1, ik), (i2, i(k-1)), ...`
   and if `k` is odd, the middle occurrence goes to the palindrome center.
   Any "crossing" pairing creates extra swaps.

4. **We can build the target permutation directly (no simulation of swaps)**
   Store positions of each character in a deque; take from both ends to form pairs.

---

## 3) Full solution approach

### Step A: Check if palindrome is possible
- Collect the positions of each letter into a per-character deque.
- Count how many letters have odd frequency (`oddCnt`).
- If `oddCnt != n % 2`, print `-1`.

### Step B: Build the target index-permutation `p`
We want `p[0..n-1]` where each element is an original index. This fixes the final palindrome arrangement in terms of *which original occurrences go where*.

Data structure:
- For each character `c`, keep a `deque<int> pos[c]` of all indices where `c` occurs (in increasing order).

Construction (greedy, right-to-left):
- Maintain `L = 0` (next free slot on left of palindrome), `R = n-1` (next free slot on right).
- Maintain `used[i]` to skip indices already assigned.
- Iterate `r` from `n-1` down to `0`:
  - if `used[r]`, continue.
  - If `pos[s[r]]` has size `1`, this index must go to center: `p[n/2] = r`.
  - Otherwise pair `r` with the leftmost remaining occurrence `l = pos[s[r]].front()`:
    - Place `l` at `p[L]`, `r` at `p[R]`
    - `L++`, `R--`
    - Pop `l` from front and `r` from back, mark both used.

This exactly enforces pairing `(leftmost, rightmost)` for each letter.

### Step C: Count inversions of `p`
- Use merge-sort inversion counting in `O(n log n)` (works for `n=1e6`).
- Output that inversion count as the minimum adjacent swaps.

Complexities:
- Building deques + greedy: `O(n)`
- Inversions: `O(n log n)`
- Memory: `O(n)`

---

## 4) C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

string s;

void read() { cin >> s; }

int64_t count_inversions(vector<int>& a) {
    int64_t inv = 0;
    int n = a.size();
    vector<int> temp(n);

    function<void(int, int)> merge_sort = [&](int l, int r) {
        if(l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        merge_sort(l, mid);
        merge_sort(mid + 1, r);

        int i = l, j = mid + 1, k = l;
        while(i <= mid && j <= r) {
            if(a[i] <= a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
                inv += mid - i + 1;
            }
        }
        while(i <= mid) {
            temp[k++] = a[i++];
        }
        while(j <= r) {
            temp[k++] = a[j++];
        }
        for(int i = l; i <= r; i++) {
            a[i] = temp[i];
        }
    };

    merge_sort(0, n - 1);
    return inv;
}

void solve() {
    // There is a fairly straight forward greedy which we can optimize with
    // interval trees or inversions. Let's start with fixing the middle
    // character when |s| is odd - it's going to be the unique odd frequency
    // element. Afterwards, the greedy will go from the back, say currently it's
    // s[i], it will try to find the first occurrences s[f] == s[i], and move
    // s[f] to the front. It might not be immediately clear why this is correct,
    // but we can think of the contributions and how the matches will look.
    //
    // First off, for some character C, let the positions where it occurs in s
    // be i[1], ..., i[k]. It's not hard to see that we will match (i[1], i[k]),
    // (i[2], i[k - 1]) and so on, as otherwise we will make irrelevant swaps
    // between some of these pairs. Also, if k is odd, then i[(k + 1) / 2] will
    // be in the middle.
    //
    // We already handled the case of |s| being odd as we know what goes to the
    // middle. We now have split all positions into |s| / 2 pairs (l[i], r[i]).
    // We can think of the minimum number of swaps as sum of contributions
    // between each pair of pairs. In particular, we will never swap two
    // elements from the same pair (as they are equal and it doesn't make
    // sense), and for each pair of pairs we will make either 0 or 1 swaps.
    // Let's consider a few cases:
    //
    //     1) (l[i], r[i]) fully overlaps or is fully covered by (l[j], r[j]).
    //        In this case, we will never make a swap between these two pairs.
    //        It's clear that in the final solution it just makes sense for the
    //        outer pair to cover the inner one, so we can coordinate the swaps
    //        to have this covering invariant always held.
    //
    //     2) (l[i], r[i]) and (l[j], r[j]) intersect. Then we certainly need to
    //        break this intersection at some point so that one of them covers
    //        the other. After this is broken, we are essentially left with (1)
    //        which we can always maintain. Pairs like this contribute 1 to
    //        the answer.
    //
    // Both of the above contributions will be held no matter what palindrome we
    // go for (noting that we have the assumption of an optimal matching of the
    // equal characters). It's not hard to observe that the greedy does exactly
    // that. If we only keep (1) and (2), unfortunately we will be left with a
    // "tree" structure in terms of the covering of the intervals. However, to
    // have a palindrome, we actually want a chain - in particular, we want
    // there to be nested intervals (1, |s|), (2, |s|-1) and so on. The issues
    // comes from pairs that have both (l[i], r[i]) in one of the halves. Let's
    // say we have A such pairs with both endpoints in the left halve. Then we
    // also have A endpoints with both halves on the right side. The only
    // contribution we haven't accounted for is coming from these. Let's think
    // what the greedy would do - when faced with such an interval, it will
    // either be the leftmost or rightmost (based on L/R), and place one of the
    // endpoints on the opposite end. We can convince ourselves that this is
    // optimal by considering the relative order of pairs in each of these
    // halves. It never makes sense to swap the order of two pairs in the same
    // side, as we just gain 2 additional swaps for nothing. This means the
    // leftmost or rightmost such pair will become the outermost one, and the
    // greedy does precisely that.
    //
    // All in all, the above should convince ourselves that the greedy is
    // correct, but now we want to implement it O(n log n) as that's what's
    // required by this problem. The easiest way is to create a target
    // permutation we want to achieve rather than actually doing the swaps. This
    // is fairly easy if we run the greedy. We then will simply find the number
    // of inversions in the permutation.

    map<char, deque<int>> pos;
    for(int i = 0; i < (int)s.size(); i++) {
        pos[s[i]].push_back(i);
    }

    int cnt_odd = 0;
    for(auto [c, p]: pos) {
        cnt_odd += p.size() % 2;
    }

    if(cnt_odd != s.size() % 2) {
        cout << -1 << endl;
        return;
    }

    int l_p = 0, r_p = s.size() - 1;
    vector<int> p(s.size());
    vector<bool> used(s.size());

    for(int r = (int)s.size() - 1; r >= 0; r--) {
        if(used[r]) {
            continue;
        }

        used[r] = true;
        if(pos[s[r]].size() == 1) {
            p[s.size() / 2] = r;
            continue;
        }

        int l = pos[s[r]].front();
        pos[s[l]].pop_front();
        pos[s[r]].pop_back();

        used[l] = true;
        p[l_p++] = l;
        p[r_p--] = r;
    }

    cout << count_inversions(p) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

Notes:
- `n` can be 1,000,000, so Python must be careful with performance.
- The inversion count is the main cost (`O(n log n)`); implement an **iterative merge sort** to avoid recursion depth issues.

```python
import sys
from collections import deque

# -------- inversion count via iterative merge sort (O(n log n)) --------
def count_inversions(a):
    """
    Counts inversions in a (list of ints) using iterative merge sort.
    Inversion = pair (i<j) with a[i] > a[j].
    """
    n = len(a)
    temp = [0] * n
    inv = 0

    width = 1
    while width < n:
        for left in range(0, n, 2 * width):
            mid = min(left + width, n)
            right = min(left + 2 * width, n)

            i, j, k = left, mid, left
            while i < mid and j < right:
                if a[i] <= a[j]:
                    temp[k] = a[i]
                    i += 1
                else:
                    temp[k] = a[j]
                    j += 1
                    inv += (mid - i)  # remaining left part are inversions
                k += 1

            while i < mid:
                temp[k] = a[i]
                i += 1
                k += 1
            while j < right:
                temp[k] = a[j]
                j += 1
                k += 1

            # copy merged segment back
            a[left:right] = temp[left:right]

        width *= 2

    return inv

def solve(s: str) -> int:
    n = len(s)

    # Positions for each character in a deque
    pos = [deque() for _ in range(26)]
    freq = [0] * 26

    for i, ch in enumerate(s):
        c = ord(ch) - 65
        pos[c].append(i)
        freq[c] += 1

    # Feasibility check
    odd = sum(f & 1 for f in freq)
    if odd != (n & 1):
        return -1

    # Build p[final_pos] = original_index
    p = [0] * n
    used = bytearray(n)  # memory-efficient boolean array

    L, R = 0, n - 1
    center = n // 2

    for r in range(n - 1, -1, -1):
        if used[r]:
            continue
        used[r] = 1
        c = ord(s[r]) - 65

        if len(pos[c]) == 1:
            p[center] = r
            pos[c].pop()  # consume
            continue

        l = pos[c][0]
        pos[c].popleft()  # remove l
        pos[c].pop()      # remove r
        used[l] = 1

        p[L] = l
        p[R] = r
        L += 1
        R -= 1

    return count_inversions(p)

if __name__ == "__main__":
    s = sys.stdin.readline().strip()
    print(solve(s))
```

This approach avoids simulating swaps directly and reduces the problem to building an optimal palindrome index mapping and counting inversions, which is exactly the minimal number of adjacent swaps.
