Flying Sort (Hard Version) (Codeforces 1367F2)
Tags: Greedy, two pointers

This is a hard version of the problem. In this version, the given array can contain equal elements and the constraints on $$$n$$$ are greater than in the easy version of the problem.You are given an array $$$a$$$ of $$$n$$$ integers (the given array can contain equal elements). You can perform the following operations on array elements:  choose any index $$$i$$$ ($$$1 \le i \le n$$$) and move the element $$$a[i]$$$ to the begin of the array;  choose any index $$$i$$$ ($$$1 \le i \le n$$$) and move the element $$$a[i]$$$ to the end of the array. For example, if $$$n = 5$$$, $$$a = [4, 7, 2, 2, 9]$$$, then the following sequence of operations can be performed:   after performing the operation of the first type to the second element, the array $$$a$$$ will become $$$[7, 4, 2, 2, 9]$$$;  after performing the operation of the second type to the second element, the array $$$a$$$ will become $$$[7, 2, 2, 9, 4]$$$. You can perform operations of any type any number of times in any order.Find the minimum total number of operations of the first and second type that will make the $$$a$$$ array sorted in non-decreasing order. In other words, what is the minimum number of operations must be performed so the array satisfies the inequalities $$$a[1] \le a[2] \le \ldots \le a[n]$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test. Then $$$t$$$ test cases follow.Each test case starts with a line containing an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array $$$a$$$.Then follow $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — an array that needs to be sorted by the given operations. The given array can contain equal elements.The sum of $$$n$$$ for all test cases in one test does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case output one integer — the minimum total number of operations of the first and second type, which will make the array sorted in non-decreasing order.

Note: In the first test case, you first need to move two 2, to the beginning of the array. Therefore, the desired sequence of operations: $$$[4, 7, 2, 2, 9] \rightarrow [2, 4, 7, 2, 9] \rightarrow [2, 2, 4, 7, 9]$$$.In the second test case, you need to move the 1 to the beginning of the array, and the 8 — to the end. Therefore, the desired sequence of operations: $$$[3, 5, 8, 1, 7] \rightarrow [1, 3, 5, 8, 7] \rightarrow [1, 3, 5, 7, 8]$$$.In the third test case, the array is already sorted.

Sample Inputs:
9
5
4 7 2 2 9
5
3 5 8 1 7
5
1 2 2 4 5
2
0 1
3
0 1 0
4
0 1 0 0
4
0 1 0 1
4
0 1 0 2
20
16 15 1 10 0 14 0 10 3 9 2 5 4 5 17 9 10 20 0 9

Sample Outputs:
2
2
0
0
1
1
1
1
16

Solution (Python):
import sys

def minp():
    return sys.stdin.readline().strip()

def mint():
    return int(minp())

def mints():
    return map(int, minp().split())

def solve():
    n = mint()
    b = [None] * n
    i = 0
    for v in mints():
        b[i] = (v, i)
        i += 1
    b.sort()
    c = [0] * n
    ans = int(1000000000.0)
    s = None
    i = 0
    while i < n:
        j = i + 1
        v = b[i][0]
        while j < n and b[j][0] == v:
            j += 1
        if s is None:
            for z in range(i, j):
                c[z] = j - z - 1
            ans = n - j
        else:
            k = s
            while k < e and b[k][1] < b[i][1]:
                k += 1
            for z in range(i, j - 1):
                c[z] = j - z - 1 + e
            if k == e:
                c[j - 1] = c[e - 1]
            else:
                c[j - 1] = s + e - k
            v = n - i - j
            for z in range(i, j):
                while k < e and b[k][1] < b[z][1]:
                    k += 1
                ans = min(ans, z + (e if k == s else c[k - 1]) + v)
        (s, e, i) = (i, j, j)
    print(ans)
for i in range(mint()):
    solve()

Solution (Python):
import sys

def minp():
    return sys.stdin.readline().strip()

def mint():
    return int(minp())

def mints():
    return map(int, minp().split())

def solve():
    n = mint()
    b = [None] * n
    i = 0
    for v in mints():
        b[i] = (v, i)
        i += 1
    b.sort()
    c = [0] * n
    ans = int(1000000000.0)
    s = None
    i = 0
    while i < n:
        j = i + 1
        v = b[i][0]
        while j < n and b[j][0] == v:
            j += 1
        if s is None:
            for z in range(i, j):
                c[z] = j - z - 1
            ans = n - j
        else:
            k = s
            while k < e and b[k][1] < b[i][1]:
                k += 1
            for z in range(i, j - 1):
                c[z] = j - z - 1 + e
            if k == e:
                c[j - 1] = c[e - 1]
            else:
                c[j - 1] = s + e - k
            v = n - i - j
            for z in range(i, j):
                while k < e and b[k][1] < b[z][1]:
                    k += 1
                ans = min(ans, z + (e if k == s else c[k - 1]) + v)
        (s, e, i) = (i, j, j)
    print(ans)
for i in range(mint()):
    solve()

Solution (Python):
import sys

def minp():
    return sys.stdin.readline().strip()

def mint():
    return int(minp())

def mints():
    return map(int, minp().split())

def solve():
    n = mint()
    i = 0
    b = [None] * n
    a = list(mints())
    for v in a:
        b[i] = (v, i)
        i += 1
    b.sort()
    i = 0
    c1 = [0] * n
    p = [0] * n
    prev = None
    ans = int(1000000000.0)
    while i < n:
        j = i + 1
        v = b[i][0]
        while j < n and b[j][0] == v:
            j += 1
        if prev is None:
            for z in range(i, j):
                c1[z] = j - z - 1
            for z in range(i, 1):
                ans = min(ans, z - i + n - j)
        else:
            (s, e) = prev
            k = s
            while k < e and b[k][1] < b[i][1]:
                k += 1
            for z in range(i, j - 1):
                c1[z] = j - z - 1 + e
            for z in range(j - 1, j):
                if k == e:
                    c1[z] = c1[e - 1]
                else:
                    c1[z] = s + e - k
            for z in range(i, j):
                while k < e and b[k][1] < b[z][1]:
                    k += 1
                if k == s:
                    ans = min(ans, z - i + e + n - j)
                else:
                    ans = min(ans, z - i + c1[k - 1] + n - j)
        prev = (i, j)
        i = j
    print(ans)
for i in range(mint()):
    solve()