Read problem statements in [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given a sequence of positive integers $A_{1}, A_{2}, \ldots, A_{N}$. You should make all its elements equal by performing a sequence of operations.

In one operation, you may choose any contiguous subsequence $A_{l}, A_{l+1}, \ldots, A_{r}$ such that for each $i$ ($l+1 ≤ i ≤ r$), $A_{i} = A_{l}$, i.e. a sequence of identical elements, then choose any integer $x < A_{l}$, and for each $i$ ($l ≤ i ≤ r$), replace $A_{i}$ by $x$. The integers $x$ chosen in different operations may be different.

Find the smallest number of operations necessary to make all elements of the given sequence equal.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
Print a single line containing one integer ― the smallest number of operations.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 5 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (50 points):
$A_{i} ≤ N$ for each valid $i$
the sum of $N$ over all test cases does not exceed $5,000$

Subtask #2 (50 points): original constraints

----- Sample Input 1 ------ 
2

5

5 9 8 3 12

2

19 19
----- Sample Output 1 ------ 
4

0

Difficulty: VERY_HARD
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	top = -1
	st = []
	co = 0
	for i in arr:
		while len(st) and st[-1] > i:
			st.pop()
			co += 1
		if len(st) and st[-1] == i:
			st.pop()
		st.append(i)
	co += len(st) - 1
	print(co)


from sys import stdin
for __ in range(int(stdin.readline())):
	n = int(stdin.readline())
	nums = list(map(int, stdin.readline().split()))

	def solve(array, i, j):
		smallest = array[i]
		sets = [[i, i]]
		for k in range(i + 1, j):
			if array[k] == smallest:
				if sets[-1][1] + 1 == k:
					sets[-1][1] += 1
				else:
					sets.append([k, k])
			elif array[k] < smallest:
				smallest = array[k]
				sets = [[k, k]]
		sets = [[i - 1, i - 1]] + sets + [[j, j]]
		ans = 1
		for i in range(1, len(sets)):
			if sets[i - 1][1] + 1 < sets[i][0]:
				ans += solve(array, sets[i - 1][1] + 1, sets[i][0])
		return ans
	print(solve(nums, 0, n) - 1)


from collections import defaultdict
from heapq import *
import itertools, math

def parse_integer_list():
	return [int(x) for x in input().split()]
from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
	hi = hi if hi is not None else len(a)
	pos = bisect_left(a, x, lo, hi)
	return pos

def handle_input(A, N):
	B = [A[0]]
	for i in range(len(A)):
		if B[-1] != A[i]:
			B.append(A[i])
	min_val = min(B)
	cnt = len(B) - B.count(min_val)
	l = [B[0]]
	for i in range(1, len(B)):
		b = B[i]
		idx = binary_search(l, b)
		if idx == len(l):
			l.append(b)
			continue
		if l[idx] == b:
			if b != min_val:
				cnt -= 1
			l = l[:idx + 1]
		else:
			l = l[:idx]
			l.append(b)
	return cnt
T = int(input())
for i in range(T):
	N = int(input())
	A = parse_integer_list()
	print(handle_input(A, N))


def abc(l, n):
	if n == 0:
		return -1
	if n == 1:
		return 0
	x = min(l)
	i = 0
	k = []
	ans = 0
	while i < n:
		if l[i] == x:
			ans += 1 + abc(k, len(k))
			k = []
			i += 1
			continue
		k.append(l[i])
		i += 1
	ans += 1 + abc(k, len(k))
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	k = []
	x = min(l)
	for i in l:
		if i == x:
			ans += 1 + abc(k, len(k))
			k = []
		else:
			k.append(i)
	ans += 1 + abc(k, len(k))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	stack = []
	ans = 0
	for i in range(n):
		while stack and stack[-1] > arr[i]:
			stack.pop()
			ans += 1
		if not stack or arr[i] > stack[-1]:
			stack.append(arr[i])
	print(ans + len(stack) - 1)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = input().strip().split()
	for i in range(len(arr)):
		arr[i] = int(arr[i])
	stack = []
	top = -1
	ans = 0
	for i in range(n):
		if top == -1:
			stack.append(arr[i])
			top += 1
		elif arr[i] == stack[top]:
			continue
		elif arr[i] > stack[top]:
			stack.append(arr[i])
			top += 1
		else:
			while top != -1 and stack[top] > arr[i]:
				stack.pop()
				ans += 1
				top -= 1
			if top == -1:
				stack.append(arr[i])
				top += 1
			elif arr[i] == stack[top]:
				continue
			else:
				stack.append(arr[i])
				top += 1
	ans += top
	print(ans)


import sys
sys.setrecursionlimit(10 ** 9)

def find(a):
	global par
	if par[a] == a:
		return a
	par[a] = find(par[a])
	return par[a]
t = int(input())
for _ in range(t):
	n = int(input())
	it = list(map(int, input().split()))
	aa = [[0, 0, it[0]]]
	for i in range(1, n):
		if it[i] == it[i - 1]:
			aa[-1][1] += 1
		else:
			aa.append([i, i, it[i]])
	aa.sort()
	aa = [i + [j] for (j, i) in enumerate(aa)]
	aa.sort(key=lambda x: [-x[2], x[3]])
	bb = [[aa[0]]]
	vis = [0] * n
	for i in range(1, len(aa)):
		if aa[i][2] == aa[i - 1][2]:
			bb[-1].append(aa[i])
		else:
			bb.append([aa[i]])
	par = [i for i in range(len(aa))]
	tot = 0
	for j in bb[:-1]:
		k = 0
		for i in j:
			if k == len(j) - 1:
				par[i[3]] = min(i[3] + 1, len(aa) - 1)
				tot += 1
				k += 1
				continue
			x = find(i[3] + 1)
			if j[k + 1][3] == x:
				k += 1
				par[i[3]] = i[3] + 1
				continue
			else:
				tot += 1
				if i[3] != 0:
					par[i[3]] = min(i[3] + 1, len(aa) - 1)
			k += 1
	print(tot)