<p>You are given two <strong>0-indexed</strong> integer arrays <code>nums1</code> and <code>nums2</code>, of equal length <code>n</code>.</p>

<p>In one operation, you can swap the values of any two indices of <code>nums1</code>. The <strong>cost</strong> of this operation is the <strong>sum</strong> of the indices.</p>

<p>Find the <strong>minimum</strong> total cost of performing the given operation <strong>any</strong> number of times such that <code>nums1[i] != nums2[i]</code> for all <code>0 &lt;= i &lt;= n - 1</code> after performing all the operations.</p>

<p>Return <em>the <strong>minimum total cost</strong> such that </em><code>nums1</code> and <code>nums2</code><em> satisfy the above condition</em>. In case it is not possible, return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,3,4,5], nums2 = [1,2,3,4,5]
<strong>Output:</strong> 10
<strong>Explanation:</strong> 
One of the ways we can perform the operations is:
- Swap values at indices 0 and 3, incurring cost = 0 + 3 = 3. Now, nums1 = [4,2,3,1,5]
- Swap values at indices 1 and 2, incurring cost = 1 + 2 = 3. Now, nums1 = [4,3,2,1,5].
- Swap values at indices 0 and 4, incurring cost = 0 + 4 = 4. Now, nums1 =[5,3,2,1,4].
We can see that for each index i, nums1[i] != nums2[i]. The cost required here is 10.
Note that there are other ways to swap values, but it can be proven that it is not possible to obtain a cost less than 10.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [2,2,2,1,3], nums2 = [1,2,2,3,3]
<strong>Output:</strong> 10
<strong>Explanation:</strong> 
One of the ways we can perform the operations is:
- Swap values at indices 2 and 3, incurring cost = 2 + 3 = 5. Now, nums1 = [2,2,1,2,3].
- Swap values at indices 1 and 4, incurring cost = 1 + 4 = 5. Now, nums1 = [2,3,1,2,2].
The total cost needed here is 10, which is the minimum possible.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums1 = [1,2,2], nums2 = [1,2,2]
<strong>Output:</strong> -1
<strong>Explanation:</strong> 
It can be shown that it is not possible to satisfy the given conditions irrespective of the number of operations we perform.
Hence, we return -1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == nums1.length == nums2.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums1[i], nums2[i] &lt;= n</code></li>
</ul>

class Solution:
    def minimumTotalCost(self, nums1: List[int], nums2: List[int]) -> int:
        # Firstly, we extract all the bad indices I (nums1[i] == nums2[i]).
        # 1. The most dominant element frequency <= len(I) // 2.
        # If len(I) is even, we can sort I by nums[i]. Apparently, for any I[j], we have I[j + len(I) // 2] != I[j], otherwise we will have len(I) // 2 + 1 identical elements, which is a contradiction. So in this case, we can swap each pair (j, j + len(I) // 2) such that each index is swapped for exactly once. The answer is sum(I).
        # If len(I) is odd:
        # 1.1 If 0 is not in I, we want to find a target i such that nums2[0] != nums1[i] and nums1[0] != nums2[i]. Also nums2[0] != nums1[0]. So nums1[0], nums2[0] and nums1[i] are distinct. For the worst case, nums1[0] and nums2[0] equal to some values in nums1[I], and we want to choose the 3rd value in nums1[I] to swap with index 0. It is possible because len(I) = 2 * (len(I) // 2) + 1.
        # 1.2 We can find nums1[i] != nums1[j] such that nums1[i], nums1[j] are two most frequency elements in nums1[I] not equal to nums1[0], and swap (0, i) and (0, j). As a result, 0, i, j are swapped expectedly. The new length will be len(I) - 3 which is even. Doing so must decrement the two most frequency elements in nums1[I] in the new array. The two most frequency elements have frequency <= len(I) // 2, so after the operation their frequency will be <= len(I) // 2 - 1. It still holds for the even case.
        # 2. The most dominant element frequency > len(I) // 2.
        # We must include more elements for swapping, otherwise the solution would not be possible. To include new elements, we can scan the array from small index to large index to see if we can consume dominant elements. The swapping target i should have nums1[i] != dominant and nums2[i] != dominant, otherwise the swapping will not meet the constraint. Once we do this, we manage to decrement the number of dominant as well as len(I). Once frequency <= len(I) // 2, we can compute the swapping times by the conclusion in 1. Actually, we can also revisit this as adding an element into I, because d <= (len(I) + 1) // 2 is equivalent to d - 1 <= (len(I) - 1) // 2.
        I = [i for i in range(len(nums1)) if nums1[i] == nums2[i]]
        if len(I) == 0:
            return 0
        ct = collections.Counter([nums1[i] for i in I])
        dom_cnt = 0
        dom_num = None
        for v in ct:
            if ct[v] > dom_cnt:
                dom_cnt = ct[v]
                dom_num = v
        if dom_cnt <= (len(I) // 2):
            return sum(I)
        for i in range(len(nums1)):
            if nums1[i] != nums2[i] and nums1[i] != dom_num and nums2[i] != dom_num:
                I.append(i)
                if dom_cnt <= (len(I) // 2):
                    return sum(I)
        return -1
        
        
36200