package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

var scanner *bufio.Scanner

func init() {
	scanner = bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	const maxCapacity = 10 * 1024 * 1024
	buf := make([]byte, maxCapacity)
	scanner.Buffer(buf, maxCapacity)
}

func readInt() int {
	scanner.Scan()
	res := 0
	for _, b := range scanner.Bytes() {
		res = res*10 + int(b-'0')
	}
	return res
}

func main() {
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	t := readInt()
	for i := 0; i < t; i++ {
		solve(writer)
	}
}

func solve(writer *bufio.Writer) {
	n := readInt()
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = readInt()
	}

	sortedA := make([]int, n)
	copy(sortedA, a)
	sort.Ints(sortedA)

	uniqueA := make([]int, 0)
	if n > 0 {
		uniqueA = append(uniqueA, sortedA[0])
		for i := 1; i < n; i++ {
			if sortedA[i] != sortedA[i-1] {
				uniqueA = append(uniqueA, sortedA[i])
			}
		}
	}

	U := len(uniqueA)
	if U <= 1 {
		fmt.Fprintln(writer, 0)
		return
	}

	pos := make([][]int, U)
	for i := 0; i < n; i++ {
		v := sort.SearchInts(uniqueA, a[i])
		pos[v] = append(pos[v], i)
	}

	dp := make([]int, U)
	dp[0] = len(pos[0])
	maxKept := 0

	for v := 0; v < U; v++ {
		if v > 0 {
			firstV := pos[v][0]
			lastVMinus1 := pos[v-1][len(pos[v-1])-1]
			cntV := len(pos[v])
			if lastVMinus1 < firstV {
				dp[v] = dp[v-1] + cntV
			} else {
				c := sort.Search(len(pos[v-1]), func(i int) bool {
					return pos[v-1][i] >= firstV
				})
				dp[v] = c + cntV
			}
		}

		cand1 := dp[v]
		if v < U-1 {
			lastV := pos[v][len(pos[v])-1]
			idx := sort.Search(len(pos[v+1]), func(i int) bool {
				return pos[v+1][i] > lastV
			})
			d := len(pos[v+1]) - idx
			cand1 += d
		}

		if cand1 > maxKept {
			maxKept = cand1
		}
	}

	for v := 0; v < U-1; v++ {
		currentV := 0
		currentV1 := len(pos[v+1])
		val := currentV + currentV1
		if val > maxKept {
			maxKept = val
		}

		i, j := 0, 0
		for i < len(pos[v]) || j < len(pos[v+1]) {
			if i < len(pos[v]) && (j == len(pos[v+1]) || pos[v][i] < pos[v+1][j]) {
				currentV++
				i++
			} else {
				currentV1--
				j++
			}
			val = currentV + currentV1
			if val > maxKept {
				maxKept = val
			}
		}
	}

	fmt.Fprintln(writer, n-maxKept)
}