<|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.

170. Particles
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



A new kind of elementary particles was discovered in recent physical experiments. These particles were named "buons". It was also discovered that there exist two types of buons, which were named "Y+" (psi +) and "Y-" (psi -) buons. It became known that buons tend to form chains. Moreover, a very interesting property of buons, named "going through", was discovered: if two buons with different types are neighbors in a chain, they can easily exchange places one with other.

Because one "going through" takes very short time, the order of buons in chain can quickly change. Now the physicists are interested, how many "goings through" must happen for one chain to become other.

You are to help them. Write a program, which determines the minimal number of "goings through" which will allow one chain to become other.

Input
First two lines of input contains strings of "+" and "-" characters, describing first and second buon chains. The "+" character stands for Y+ buon, and "-" character stands for Y- buon. The length of each string doesn't exceed 5000; moreover, there is at leat one buon in each chain.

Output
If it is possible to make the second chain from the first, using only "goings trough", write on the first line of output the minimal number K of "goings through" which are required. If it is impossible to make the secong chain from the first, output only integer "-1".

Sample test(s)

Input
++-+--+
-++--++

Output
4
Author:	NNSU #2 team
Resource:	Compiled from many sources
Date:

<|response|>
1. Abridged Problem Statement  
Given two strings A and B of equal length n (n ≤ 5000), each character is either '+' or '-'. You may repeatedly swap any adjacent pair “+-” into “-+”. Determine the minimum number of such swaps (called “goings through”) needed to transform A into B, or output –1 if it is impossible.

2. Key Observations  
- A swap only exchanges a ‘+’ and a ‘–’ when they are adjacent.  
- You can never change the relative order of the ‘+’ characters among themselves, nor the relative order of the ‘–’ characters among themselves.  
- Hence, transforming A into B is possible if and only if A and B have the same total number of ‘+’ characters (and thus the same number of ‘–’ characters).  
- If possible, label the ‘+’ characters in A from 1…k in left-to-right order, and do the same in B; likewise label the ‘–’ from 1…m in each string.  
- Each character in A has a unique matching character in B (the same label and same sign).  
- Build an array P of length n so that P[i] = index in B of the character that matches A[i].  
- Each adjacent swap of “+-” ↔ “-+” in A corresponds to swapping two adjacent entries in P. The minimum number of such adjacent swaps needed to reorder P into sorted order is exactly the inversion count of P.

3. Full Solution Approach  
a) Read strings A and B.  
b) Scan A to record two lists: posA = positions of '+'; negA = positions of '-'.  
   Do the same for B: posB, negB.  
c) If posA.size() ≠ posB.size(), print –1 and stop.  
d) We want to match the i-th plus in A to the i-th plus in B, and similarly each minus.  
   To build P in a single left-to-right pass on A, reverse posB and negB (so we can pop from the back).  
e) Initialize empty array P. For i = 0…n–1:  
   - If A[i] == '+', take idx = posB.back(), pop_back(), and append idx to P.  
   - Else (A[i] == '-'), take idx = negB.back(), pop_back(), and append idx to P.  
f) Compute the inversion count of P in O(n log n) by a merge-sort based routine.  
g) Print the inversion count.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Merge-sort based inversion counting on an integer array.
// Returns number of inversions, and sorts the array in place.
long long countInversions(vector<int>& a, int left, int right) {
    if (left >= right)
        return 0;
    int mid = (left + right) >> 1;
    long long inv = countInversions(a, left, mid)
                  + countInversions(a, mid+1, right);
    vector<int> temp;
    temp.reserve(right - left + 1);
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp.push_back(a[i++]);
        } else {
            // a[i] > a[j] => each remaining element a[i..mid] 
            // forms an inversion with a[j].
            temp.push_back(a[j++]);
            inv += (mid - i + 1);
        }
    }
    while (i <= mid) temp.push_back(a[i++]);
    while (j <= right) temp.push_back(a[j++]);
    // Copy back
    for (int k = left; k <= right; k++)
        a[k] = temp[k - left];
    return inv;
}

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

    string A, B;
    cin >> A >> B;
    int n = A.size();
    // Record positions of '+' and '-' in A and in B
    vector<int> posA, negA, posB, negB;
    for (int i = 0; i < n; i++) {
        if (A[i] == '+') posA.push_back(i);
        else             negA.push_back(i);
        if (B[i] == '+') posB.push_back(i);
        else             negB.push_back(i);
    }
    // If counts differ, impossible
    if (posA.size() != posB.size()) {
        cout << -1 << "\n";
        return 0;
    }

    // We will build permutation P by matching in order.
    // Reverse target lists so we can pop from back in O(1).
    reverse(posB.begin(), posB.end());
    reverse(negB.begin(), negB.end());

    vector<int> P;
    P.reserve(n);
    for (int i = 0; i < n; i++) {
        if (A[i] == '+') {
            // match to the next '+' position in B
            P.push_back(posB.back());
            posB.pop_back();
        } else {
            // match to the next '-' position in B
            P.push_back(negB.back());
            negB.pop_back();
        }
    }

    // Count inversions in P
    long long answer = countInversions(P, 0, n-1);
    cout << answer << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
sys.setrecursionlimit(10000)

def count_inversions(arr):
    # Merge-sort based inversion count
    def merge_sort(a, l, r):
        if l >= r:
            return 0
        m = (l + r) // 2
        inv = merge_sort(a, l, m) + merge_sort(a, m+1, r)
        temp = []
        i, j = l, m+1
        while i <= m and j <= r:
            if a[i] <= a[j]:
                temp.append(a[i])
                i += 1
            else:
                temp.append(a[j])
                j += 1
                inv += (m - i + 1)
        while i <= m:
            temp.append(a[i]); i += 1
        while j <= r:
            temp.append(a[j]); j += 1
        # copy back
        for k in range(l, r+1):
            a[k] = temp[k - l]
        return inv

    # Work on a copy if original must be preserved
    return merge_sort(arr, 0, len(arr)-1)

def main():
    A = sys.stdin.readline().strip()
    B = sys.stdin.readline().strip()
    n = len(A)

    posA = [i for i,ch in enumerate(A) if ch == '+']
    negA = [i for i,ch in enumerate(A) if ch == '-']
    posB = [i for i,ch in enumerate(B) if ch == '+']
    negB = [i for i,ch in enumerate(B) if ch == '-']

    # If counts differ, impossible
    if len(posA) != len(posB):
        print(-1)
        return

    # Reverse so pop() gives next match in left-to-right order
    posB.reverse()
    negB.reverse()

    P = []
    for ch in A:
        if ch == '+':
            P.append(posB.pop())
        else:
            P.append(negB.pop())

    # The answer is the inversion count of P
    print(count_inversions(P))

if __name__ == "__main__":
    main()
```