# BEGIN Yura Desk bundle: library_codex.data_structure.SegmentTree
"""Point updates and range products for an arbitrary monoid.

Use this when values change one position at a time and a half-open interval
must be folded with an associative operation.  ``max_right`` and ``min_left``
also find the first boundary where a monotone predicate stops holding.
"""


class SegmentTree:
    __slots__ = ("n", "size", "log", "data", "op", "identity")

    def __init__(self, values, op, identity):
        if isinstance(values, int):
            n = values
            values = [identity] * n
        else:
            values = list(values)
            n = len(values)
        size = 1 << (n - 1).bit_length() if n else 1
        data = [identity] * (size << 1)
        data[size : size + n] = values
        for node in range(size - 1, 0, -1):
            data[node] = op(data[node << 1], data[node << 1 | 1])
        self.n = n
        self.size = size
        self.log = size.bit_length() - 1
        self.data = data
        self.op = op
        self.identity = identity

    def set(self, index, value):
        node = index + self.size
        data = self.data
        data[node] = value
        op = self.op
        node >>= 1
        while node:
            data[node] = op(data[node << 1], data[node << 1 | 1])
            node >>= 1

    def add(self, index, value):
        """indexの現在値をop(value, current)で置き換える。O(log N)。"""
        node = index + self.size
        data = self.data
        op = self.op
        data[node] = op(value, data[node])
        node >>= 1
        while node:
            data[node] = op(data[node << 1], data[node << 1 | 1])
            node >>= 1

    def get(self, index):
        return self.data[index + self.size]

    def tolist(self):
        """現在の要素列をlistで返す。O(N)。"""
        return self.data[self.size:self.size + self.n]

    def __str__(self):
        return str(self.tolist())

    def __repr__(self):
        return "SegmentTree(%r)" % self.tolist()

    def prod(self, left, right):
        left += self.size
        right += self.size
        first = self.identity
        second = self.identity
        data = self.data
        op = self.op
        while left < right:
            if left & 1:
                first = op(first, data[left])
                left += 1
            if right & 1:
                right -= 1
                second = op(data[right], second)
            left >>= 1
            right >>= 1
        return op(first, second)

    query = prod

    def all_prod(self):
        return self.data[1]

    def max_right(self, left, predicate):
        if left == self.n:
            return self.n
        left += self.size
        value = self.identity
        data = self.data
        op = self.op
        while True:
            while not left & 1:
                left >>= 1
            merged = op(value, data[left])
            if not predicate(merged):
                while left < self.size:
                    left <<= 1
                    merged = op(value, data[left])
                    if predicate(merged):
                        value = merged
                        left += 1
                return min(left - self.size, self.n)
            value = merged
            left += 1
            if left & -left == left:
                break
        return self.n

    def min_left(self, right, predicate):
        if right == 0:
            return 0
        right += self.size
        value = self.identity
        data = self.data
        op = self.op
        while True:
            right -= 1
            while right > 1 and right & 1:
                right >>= 1
            merged = op(data[right], value)
            if not predicate(merged):
                while right < self.size:
                    right = right << 1 | 1
                    merged = op(data[right], value)
                    if predicate(merged):
                        value = merged
                        right -= 1
                return max(0, right + 1 - self.size)
            value = merged
            if right & -right == right:
                break
        return 0

    def __getitem__(self, index):
        return self.get(index)
# END Yura Desk bundle: library_codex.data_structure.SegmentTree

# BEGIN Yura Desk bundle: library_codex.data_structure.LazySegmentTree
"""Range actions and range products with lazy propagation.

Use this when one update affects every element in a half-open interval and
interval aggregates are also required.  The caller supplies the monoid, how an
action changes an aggregate, and how newer and older actions compose.
"""


class LazySegmentTree:
    __slots__ = (
        "n", "size", "log", "data", "lazy", "pending", "length",
        "op", "identity", "mapping", "composition"
    )

    def __init__(
        self,
        values,
        op,
        identity,
        mapping,
        composition,
    ):
        if isinstance(values, int):
            n = values
            values = [identity] * n
        else:
            values = list(values)
            n = len(values)
        size = 1 << (n - 1).bit_length() if n else 1
        data = [identity] * (size << 1)
        data[size : size + n] = values
        length = [0] * (size << 1)
        for index in range(size, size + n):
            length[index] = 1
        for node in range(size - 1, 0, -1):
            data[node] = op(data[node << 1], data[node << 1 | 1])
            length[node] = length[node << 1] + length[node << 1 | 1]
        self.n = n
        self.size = size
        self.log = size.bit_length() - 1
        self.data = data
        self.lazy = [None] * size
        self.pending = bytearray(size)
        self.length = length
        self.op = op
        self.identity = identity
        self.mapping = mapping
        self.composition = composition

    def _update(self, node):
        self.data[node] = self.op(
            self.data[node << 1], self.data[node << 1 | 1]
        )

    def _all_apply(self, node, action):
        self.data[node] = self.mapping(
            action, self.data[node], self.length[node]
        )
        if node < self.size:
            if self.pending[node]:
                self.lazy[node] = self.composition(action, self.lazy[node])
            else:
                self.lazy[node] = action
                self.pending[node] = 1

    def _push(self, node):
        if self.pending[node]:
            action = self.lazy[node]
            self._all_apply(node << 1, action)
            self._all_apply(node << 1 | 1, action)
            self.lazy[node] = None
            self.pending[node] = 0

    def set(self, index, value):
        node = index + self.size
        for shift in range(self.log, 0, -1):
            self._push(node >> shift)
        self.data[node] = value
        for shift in range(1, self.log + 1):
            self._update(node >> shift)

    def add(self, index, value):
        """indexの現在値をop(value, current)で置き換える。O(log N)。"""
        node = index + self.size
        for shift in range(self.log, 0, -1):
            self._push(node >> shift)
        self.data[node] = self.op(value, self.data[node])
        for shift in range(1, self.log + 1):
            self._update(node >> shift)

    def get(self, index):
        node = index + self.size
        for shift in range(self.log, 0, -1):
            self._push(node >> shift)
        return self.data[node]

    def tolist(self):
        """遅延作用を反映した現在の要素列をlistで返す。O(N)。"""
        for node in range(1, self.size):
            self._push(node)
        return self.data[self.size:self.size + self.n]

    def __str__(self):
        return str(self.tolist())

    def __repr__(self):
        return "LazySegmentTree(%r)" % self.tolist()

    def prod(self, left, right):
        if left == right:
            return self.identity
        left += self.size
        right += self.size
        for shift in range(self.log, 0, -1):
            if (left >> shift) << shift != left:
                self._push(left >> shift)
            if (right >> shift) << shift != right:
                self._push((right - 1) >> shift)
        first = self.identity
        second = self.identity
        op = self.op
        data = self.data
        while left < right:
            if left & 1:
                first = op(first, data[left])
                left += 1
            if right & 1:
                right -= 1
                second = op(data[right], second)
            left >>= 1
            right >>= 1
        return op(first, second)

    query = prod

    def apply(self, left, right=None, action=None):
        if action is None:
            index = left
            action = right
            node = index + self.size
            for shift in range(self.log, 0, -1):
                self._push(node >> shift)
            self._all_apply(node, action)
            for shift in range(1, self.log + 1):
                self._update(node >> shift)
            return
        if left == right:
            return
        left += self.size
        right += self.size
        original_left = left
        original_right = right
        for shift in range(self.log, 0, -1):
            if (left >> shift) << shift != left:
                self._push(left >> shift)
            if (right >> shift) << shift != right:
                self._push((right - 1) >> shift)
        while left < right:
            if left & 1:
                self._all_apply(left, action)
                left += 1
            if right & 1:
                right -= 1
                self._all_apply(right, action)
            left >>= 1
            right >>= 1
        left = original_left
        right = original_right
        for shift in range(1, self.log + 1):
            if (left >> shift) << shift != left:
                self._update(left >> shift)
            if (right >> shift) << shift != right:
                self._update((right - 1) >> shift)

    range_apply = apply

    def all_prod(self):
        return self.data[1]

    def max_right(self, left, predicate):
        if left == self.n:
            return self.n
        node = left + self.size
        for shift in range(self.log, 0, -1):
            self._push(node >> shift)
        value = self.identity
        while True:
            while not node & 1:
                node >>= 1
            merged = self.op(value, self.data[node])
            if not predicate(merged):
                while node < self.size:
                    self._push(node)
                    node <<= 1
                    merged = self.op(value, self.data[node])
                    if predicate(merged):
                        value = merged
                        node += 1
                return min(node - self.size, self.n)
            value = merged
            node += 1
            if node & -node == node:
                break
        return self.n

    def min_left(self, right, predicate):
        if right == 0:
            return 0
        node = right + self.size
        for shift in range(self.log, 0, -1):
            self._push((node - 1) >> shift)
        value = self.identity
        while True:
            node -= 1
            while node > 1 and node & 1:
                node >>= 1
            merged = self.op(self.data[node], value)
            if not predicate(merged):
                while node < self.size:
                    self._push(node)
                    node = node << 1 | 1
                    merged = self.op(self.data[node], value)
                    if predicate(merged):
                        value = merged
                        node -= 1
                return max(0, node + 1 - self.size)
            value = merged
            if node & -node == node:
                break
        return 0
# END Yura Desk bundle: library_codex.data_structure.LazySegmentTree

# input
import sys
input = sys.stdin.readline
II = lambda : int(input())
MI = lambda : map(int, input().split())
LI = lambda : [int(a) for a in input().split()]
SI = lambda : input().rstrip()
LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)]
LSI = lambda n : [input().rstrip() for _ in range(n)]
MI_1 = lambda : map(lambda x:int(x)-1, input().split())
LI_1 = lambda : [int(a)-1 for a in input().split()]

mod = 998244353
inf = 1001001001001001001
ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97
ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97
yes = lambda : print("Yes")
no = lambda : print("No")
yn = lambda flag : print("Yes" if flag else "No")

prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1)
alplow = "abcdefghijklmnopqrstuvwxyz"
alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)}
DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]]
DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]]
DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]]
prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59]
sys.set_int_max_str_digits(0)
# sys.setrecursionlimit(10**6)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')

from collections import defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right
DD = defaultdict
BSL = bisect_left
BSR = bisect_right



def solve():
    n = II()
    h = LI()
    
    xs = sorted(h)
    idx = {x: i for i, x in enumerate(xs)}
    
    seg = [SegmentTree([-inf] * n, max, -inf) for _ in range(4)]
    
    # のこした猫がいない
    emp = [0, -inf, -inf, -inf]

    # 全体の最大値
    mx = [-inf] * 4

    for i, x in enumerate(h):
        r = idx[x]
        rs = [n-r-1, r, n-r-1, r]
        
        keep = [-inf] * 4
        # のこす
        for p in range(4):
            q = max(emp[p], seg[p].prod(0, rs[p]))
            keep[p] = q + 1
        
        for p in range(1, 4):
            # p = 1 -> 1 ~ n-4
            if p <= i <= n - 5 + p:
                q = max(emp[p-1], seg[p-1].prod(0, rs[p-1]))
                keep[p] = max(keep[p], q + 1)
        
        pre = [max(emp[p], mx[p]) for p in range(4)]

        for p in range(1, 4):
            if p <= i <= n - 5 + p:
                emp[p] = max(emp[p], pre[p-1])
        
        for p in range(4):
            seg[p].set(rs[p], keep[p])
            mx[p] = max(mx[p], keep[p])
        
        # print(mx)

    ans = max(emp[3], mx[3])
    print(n - ans)


t = II()
for _ in range(t):
    solve()