Array Halves

I took this problem yesterday and I have submitted it's explanation on the site, and attaching the same here. The Problem Statement is provided below, try to get this one on your own, even if you are not sure about the code just try to find an idea to automate the process that you are using to find the answer. 

Problem Statement:- 

Chef has a permutation $�$ of length $2\cdot �$. He can perform the following operation on $�$:

• Select an index $�$ $(1\le �<2\cdot �)$ and swap ${�}_{�}$ and ${�}_{�+1}$.

Chef would call the permutation $�$ good, if the maximum element of the first half of $�$ is less than the minimum element of the second half of $�$.
Formally ${\displaystyle \underset{(1\le �\le �)}{\max }{�}_{�}<\underset{(�<�\le 2\cdot �)}{\min }{�}_{�}}$.

Find the minimum number of operations Chef needs to apply to make $�$ good.

Note: A permutation of length $�$ is an array where every integer from $1$ to $�$ occurs exactly once.

Input Format

• The first line contains a single integer $�$ — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer $�$ — half the size of the permutation $�$.
• The second line of each test case contains $2\cdot �$ space-separated integers ${�}_1,{�}_2,\dots ,{�}_{2\cdot �}$ denoting the permutation $�$.

Output Format

For each test case, output the minimum number of operations required to make $�$ good.

Constraints

• $1\le �\le 10^5$
• $1\le �\le 10^5$
• $�$ is a permutation of length $2\cdot �$
• The sum of $�$ over all test cases won't exceed $2\cdot 10^5$.

Sample 1:

Input

Output

3
2
3 2 1 4
3
1 2 3 4 5 6
3
6 5 4 3 2 1

2
0
9

Explanation:

Test case $1$: We can perform the following operations:

• Apply operation at $�=1$: $[3,2,1,4]\to [2,3,1,4]$
• Apply operation at $�=2$: $[2,3,1,4]\to [2,1,3,4]$

Test case $2$: $�$ is already good.

The below code was in Python3 and is a second implementation, the 1st one got rejected due to Time Constraints.

for _ in range(int(input())):

    n=int(input())

    nums=list(map(int,input().split()))

    ans=0

    itr2=n

    for i in range(n):

        elem=nums[i]

        if(elem>n):

            # Means this number doesn't belong in this half

            while(nums[itr2]>n):

                # While we keep getting the elem which belongs in the 2nd half

                itr2+=1

            # Means now we have a num which doesn't belong in the 2nd half

            # Get the dist between these 2 nums, and add to the ans

            ans+=itr2-i

            itr2+=1

    print(ans)

Explanation:-

So, this one was quite interesting, basically we had to understand the pattern that was being made in the process where we make operations to get the max elem of first half less than the minimum elem of the second half. The first thing is that the nums are from 1 to 2N, and suppose we take an example of N=2, now we know the nums are 1,2,3 and 4. Now, let's try to get the condition that is required. if we consider this order of array then the first half is 1,2 and the second one is 3,4. This is one is satisfying but, now we need to understand the idea or the logic of the problem to crack it, you need to understand that we need to make constant tweekings and assumptions to see if there is something in this. So, with that try this array with elems in descending order and also in random order, you will come to the conclusion that for satisfying the condition the nums less than or equal to N should be in the first half of the array and the other nums should be in the second half of the array. Now, we made some progress but how do we count the number of operations?? Now we will come to a conclusion after some thought and that will be that we just need to map an elem which doesn't belong in the first half to an elem which doesn't belong in the second half. Just think bout it, if an elem is in 1st half and it shouldn't be there means it is taking place of some elem that should be in 1st half but is in the 2nd half, so we need to find that elem in the 2nd half. That's what I am doing.

1. Just take the inputs, then maintain a count variable "ans".
2. Now traverse the whole 1st half of the array,
3. if we find elem which doesn't belong in the 1st half then we will find a corresponding elem that shouldn't be in 2nd half.
4. Thing to notice here is that I am declaring itr2 outside the external loop bcz I don't wan it to again traverse the same elems.
5. So, now whenever you get a pair( you will get if you get 1 in 1st half) just get the distance of indices and add it to the ans variable, bcz it adds to the overall no. of operations required. That's it, and this took me around 35mins to figure out. Peace!