<|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
- Count frequency of each letter (26 letters only).
- 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 (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Count inversions in array a using merge sort.
  Inversions = number of pairs (i < j) with a[i] > a[j].
  This equals the minimum number of adjacent swaps needed to transform
  the original order into the target order encoded by permutation a.
*/
static long long count_inversions(vector<int> &a) {
    int n = (int)a.size();
    vector<int> temp(n);
    long long inv = 0;

    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++];
                // All remaining elements in left half [i..mid] are > a[j-1]
                inv += (mid - i + 1);
            }
        }
        while (i <= mid) temp[k++] = a[i++];
        while (j <= r)   temp[k++] = a[j++];

        for (int t = l; t <= r; t++) a[t] = temp[t];
    };

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

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

    string s;
    cin >> s;
    int n = (int)s.size();

    // pos[c] = deque of indices where character c appears
    // Using array of 26 deques is faster than map for this problem.
    array<deque<int>, 26> pos;
    array<int, 26> freq{};
    freq.fill(0);

    for (int i = 0; i < n; i++) {
        int c = s[i] - 'A';
        pos[c].push_back(i);
        freq[c]++;
    }

    // Feasibility check: number of odd frequencies must be n%2
    int oddCnt = 0;
    for (int c = 0; c < 26; c++) oddCnt += (freq[c] & 1);
    if (oddCnt != (n & 1)) {
        cout << -1 << "\n";
        return 0;
    }

    // Build permutation p: p[final_position] = original_index
    vector<int> p(n);
    vector<char> used(n, 0);

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

    // Greedy construction scanning from right to left
    for (int r = n - 1; r >= 0; r--) {
        if (used[r]) continue;
        used[r] = 1;

        int c = s[r] - 'A';

        // If only one occurrence remains, it must go to the center.
        if ((int)pos[c].size() == 1) {
            p[center] = r;
            pos[c].pop_back(); // consume it (keeps structure consistent)
            continue;
        }

        // Otherwise pair r with the leftmost remaining l of same character.
        int l = pos[c].front();   // smallest index unused
        pos[c].pop_front();       // remove l
        pos[c].pop_back();        // remove r (rightmost)

        used[l] = 1;

        // Place into symmetric positions in the final palindrome
        p[L++] = l;
        p[R--] = r;
    }

    // Answer = inversions in p
    cout << count_inversions(p) << "\n";
    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.