from collections import defaultdict
import bisect


def fix_array(a):
	n = len(a)
	freq_a = defaultdict(int)
	for x in a:
		freq_a[x] += 1

	if all(a[i-1] <= a[i] for i in range(1, n)):
		return 0

	if all(a[i-1] >= a[i] for i in range(1, n)):
		return n - max(freq_a.values())

	left_side = []
	right_side = []
	inside = []
	min_pivot, max_pivot = sorted([a[0], a[n-1]])
	for x in a:
		if x < min_pivot:
			left_side.append(x)
		elif x > max_pivot:
			right_side.append(x)
		else:
			inside.append(x)

	idx_list_dict = defaultdict(list)
	for i in range(len(inside)):
		idx_list_dict[inside[i]].append(i)

	unique_inside = sorted(set(inside))

	cnt_correct_pos_left = [0 for x in unique_inside]
	cnt_correct_pos_right = [freq_a[x] for x in unique_inside]

	for i in range(len(unique_inside)-2, -1, -1):
		x = unique_inside[i]
		next_x = unique_inside[i+1]
		l_i, r_i = idx_list_dict[x][0], idx_list_dict[x][-1]
		l_i1, r_i1 = idx_list_dict[next_x][0], idx_list_dict[next_x][-1]

		if r_i < l_i1:
			cnt_correct_pos_right[i] = freq_a[x] + cnt_correct_pos_right[i+1]
		elif l_i1 < r_i < r_i1:
			# cnt_correct_pos_right[i] = freq_a[x] + sum(1 for j in idx_list_dict[next_x] if r_i < j)
			cnt_correct_pos_right[i] = freq_a[x] + len(idx_list_dict[next_x]) - bisect.bisect(idx_list_dict[next_x], r_i)
		else:
			cnt_correct_pos_right[i] = freq_a[x]

	for i in range(len(unique_inside)-1):
		x = unique_inside[i]
		next_x = unique_inside[i+1]
		l_i, r_i = idx_list_dict[x][0], idx_list_dict[x][-1]
		l_i1, r_i1 = idx_list_dict[next_x][0], idx_list_dict[next_x][-1]

		if r_i < l_i1:
			cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + freq_a[x]
		elif l_i < l_i1 < r_i:
			# cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + sum(1 for j in idx_list_dict[x] if j < l_i1)
			cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + bisect.bisect(idx_list_dict[x], l_i1)
		else:
			cnt_correct_pos_left[i+1] = 0

	# print(*zip(unique_inside, cnt_correct_pos_left, cnt_correct_pos_right))
	min_cnt_incorrect_pos = min(
		len(inside) - cnt_left - cnt_right
		for cnt_left, cnt_right in zip(cnt_correct_pos_left, cnt_correct_pos_right)
	)
	# min_cnt_incorrect_pos = min(count_incorrect_positions(unique_idx) for unique_idx in range(len(unique_inside)))
	return len(left_side) + min_cnt_incorrect_pos + len(right_side)


if __name__ == '__main__':
	test_cases = [
		[1, 3, 2, 4, 5],
		[2, 1, 4, 6, 3, 5],
		[5, 1, 3, 6, 4, 2],
		[1, 5, 2],
		[2, 1, 4, 3, 2],
		[3, 2, 5, 2, 2, 1],
		[2, 5, 4, 3, 4, 4, 4, 4, 3, 6],
		[2, 5, 4, 3, 4, 4, 4, 5, 3, 6],
		[2, 5, 4, 3, 4, 4, 3, 4, 5, 6],
	]
	for arr in test_cases:
		print(arr, fix_array(arr))