## 1) Abridged problem statement

Given a string `s` (1 ≤ |s| ≤ 1,000,000) of capital Latin letters, you may swap **adjacent** characters. Find the **minimum** number of adjacent swaps required to transform `s` into a palindrome. If it's impossible to form any palindrome (due to character counts), output `-1`.

---

## 2) Detailed editorial (solution explanation)

### Key observations

1. **When is it possible?**
   A palindrome can be formed iff:
   - If `n` is even: **all** character frequencies are even.
   - If `n` is odd: **exactly one** character frequency is odd (the middle character).

2. **Adjacent swaps and permutations**
   Adjacent swaps are exactly what's needed to transform one arrangement into another.
   If we decide a *target arrangement* in terms of **which original indices** go to which final positions, the minimum number of adjacent swaps needed equals the number of **inversions** in that index permutation.

   Why: Each adjacent swap changes inversion count by exactly 1, and bubble-sorting the permutation realizes the target with exactly that many swaps.

3. **Which occurrences of equal characters should be paired?**
   For each character `C`, suppose it occurs at indices:
   ```
   i1 < i2 < ... < ik
   ```
   In any optimal palindrome construction (min swaps), you should pair:
   ```
   (i1, ik), (i2, i(k-1)), ...
   ```
   and if `k` is odd, `i((k+1)/2)` must go to the center.

   Intuition: Crossing pairings create unnecessary "intersections" and thus extra swaps. Pairing outermost with outermost avoids this.

### Constructing the target permutation without simulating swaps

We build an array `p` of length `n`:

- `p[pos_in_final] = index_in_original`
- So `p` describes which original character (by its original index) ends up in each final position.

Then the answer is `inv(p)`.

#### Data structure
For each character, store all its indices in a deque (double-ended queue):
- front = leftmost unused occurrence
- back = rightmost unused occurrence

#### Greedy construction (right-to-left)
Maintain two pointers for final palindrome positions:
- `l_p = 0` (next free position on the left)
- `r_p = n-1` (next free position on the right)

Also keep `used[i]` to skip indices already assigned.

Process original indices `r` from `n-1` down to `0`:
- If already used, continue.
- If this character has only one unused occurrence left, it must be the center (only possible when `n` is odd):
  - set `p[n//2] = r`
- Otherwise:
  - let `l` be the leftmost unused occurrence of this same character (`deque.front()`).
  - pair `(l, r)`:
    - place `l` to `p[l_p]`, place `r` to `p[r_p]`
    - increment `l_p`, decrement `r_p`
    - mark both `l` and `r` used, pop from deque ends.

This constructs a valid palindrome mapping that corresponds to the optimal pairing described earlier.

### Why the inversion count is the minimum swaps

- We never need to swap identical letters among themselves (pointless).
- The pairing strategy avoids crossings between pairs of equal letters; any crossing would force at least one swap to "uncross".
- Once we commit to the pairing, the remaining freedom is only how these pairs nest into the final palindrome; the above greedy produces the correct nesting order without adding extra swaps.
- Given the target index order `p`, transforming original indices into that order requires exactly `inv(p)` adjacent swaps, and no solution can do better for that same mapping.

### Complexity

- Building deques: `O(n)`
- Greedy construction: `O(n)`
- Counting inversions with merge sort: `O(n log n)`
- Memory: `O(n)`

Works for `n` up to 1,000,000.

---

## 3) C++ Solution

```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;
}
```

---

## 4) Python solution (same idea) with detailed comments

```python
import sys
from collections import deque, defaultdict

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

    # width: current size of blocks to merge (1,2,4,...)
    width = 1
    while width < n:
        # merge blocks [l:l+width) and [l+width:l+2*width)
        for l in range(0, n, 2 * width):
            mid = min(l + width, n)
            r = min(l + 2 * width, n)

            i, j, k = l, mid, l
            while i < mid and j < r:
                if arr[i] <= arr[j]:
                    temp[k] = arr[i]
                    i += 1
                else:
                    temp[k] = arr[j]
                    j += 1
                    # all remaining in left block (i..mid-1) are > arr[j-1]
                    inv += (mid - i)
                k += 1

            while i < mid:
                temp[k] = arr[i]
                i += 1
                k += 1
            while j < r:
                temp[k] = arr[j]
                j += 1
                k += 1

            # copy back
            arr[l:r] = temp[l:r]

        width *= 2

    return inv

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

    # Collect positions for each character in a deque.
    pos = defaultdict(deque)
    for i, ch in enumerate(s):
        pos[ch].append(i)

    # Check palindrome feasibility by counting odd frequencies.
    cnt_odd = sum((len(d) % 2) for d in pos.values())
    if cnt_odd != (n % 2):
        return -1

    # p[final_position] = original_index placed there
    p = [0] * n
    used = [False] * n

    left_final = 0
    right_final = n - 1

    # Greedy pairing from right to left (mirror the C++ approach)
    for r in range(n - 1, -1, -1):
        if used[r]:
            continue

        used[r] = True
        ch = s[r]

        # If this is the only remaining occurrence, it must go to the center.
        if len(pos[ch]) == 1:
            p[n // 2] = r
            pos[ch].pop()   # consume it (optional, but keeps structure consistent)
            continue

        # Pair r with the leftmost remaining occurrence l.
        l = pos[ch][0]      # leftmost index of this character
        pos[ch].popleft()   # remove l
        pos[ch].pop()       # remove r (rightmost)

        used[l] = True

        # Place them in symmetric final positions
        p[left_final] = l
        p[right_final] = r
        left_final += 1
        right_final -= 1

    # Minimum adjacent swaps equals inversion count of p
    return count_inversions(p)

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

---

## 5) Compressed editorial

- A palindrome is possible iff the number of odd-frequency letters equals `n % 2`. Otherwise print `-1`.
- For each character, store all occurrence indices in a deque.
- Build a target index permutation `p` for the palindrome:
  - Keep `L=0, R=n-1`.
  - Scan indices `r` from `n-1` to `0`, skipping used.
  - If the character's deque has size 1, place `r` at `p[n//2]` (center).
  - Else pair `r` with the deque's front `l`, put `l` at `p[L]`, `r` at `p[R]`, advance `L`, decrease `R`.
- The minimum adjacent swaps needed to reach that target arrangement equals the inversion count of `p`. Compute inversions with merge sort in `O(n log n)`.
