For a given sequence of distinct non-negative integers $(b_1, b_2, \dots, b_k)$ we determine if it is good in the following way:

Consider a graph on $k$ nodes, with numbers from $b_1$ to $b_k$ written on them.

For every $i$ from $1$ to $k$: find such $j$ ($1 \le j \le k$, $j\neq i$), for which $(b_i \oplus b_j)$ is the smallest among all such $j$, where $\oplus$ denotes the operation of bitwise XOR ( https://en.wikipedia.org/wiki/Bitwise_operation#XOR ). Next, draw an undirected edge between vertices with numbers $b_i$ and $b_j$ in this graph.

We say that the sequence is good if and only if the resulting graph forms a tree (is connected and doesn't have any simple cycles).

It is possible that for some numbers $b_i$ and $b_j$, you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

You can find an example below (the picture corresponding to the first test case).

Sequence $(0, 1, 5, 2, 6)$ is not good as we cannot reach $1$ from $5$.

However, sequence $(0, 1, 5, 2)$ is good.

You are given a sequence $(a_1, a_2, \dots, a_n)$ of distinct non-negative integers. You would like to remove some of the elements (possibly none) to make the remaining sequence good. What is the minimum possible number of removals required to achieve this goal?

It can be shown that for any sequence, we can remove some number of elements, leaving at least $2$, so that the remaining sequence is good.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 200,000$) — length of the sequence.

The second line contains $n$ distinct non-negative integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the sequence.


-----Output-----

You should output exactly one integer — the minimum possible number of elements to remove in order to make the remaining sequence good.


-----Examples-----

Input
5
0 1 5 2 6
Output
1
Input
7
6 9 8 7 3 5 2
Output
2


-----Note-----

Note that numbers which you remove don't impact the procedure of telling whether the resulting sequence is good.

It is possible that for some numbers $b_i$ and $b_j$, you will try to add the edge between them twice. Nevertheless, you will add this edge only once.

Source: codeforces | Difficulty: HARD
Tags: Bit manipulation

Sorting

Tree algorithms

Dynamic programming

Divide and conquer

Data structures


Solutions:
n = int(input())
l = list(map(int, input().split()))

def fun(a):
	if len(a) <= 3:
		return len(a)
	maxE = max(a)
	if maxE == 0:
		return len(a)
	msb = 1
	while 2 * msb <= maxE:
		msb *= 2
	l1 = []
	l2 = []
	for x in a:
		if x >= msb:
			l1.append(x - msb)
		else:
			l2.append(x)
	max1 = fun(l1)
	max2 = fun(l2)
	if max1 == 0:
		return max2
	if max2 == 0:
		return max1
	return max(1 + max1, 1 + max2)
print(n - fun(l))


import math
n = int(input())
A = list(map(int, input().split()))
A.sort()

def dfs(A):
	if len(A) == 1:
		return 1
	k = 1 << int(math.log2(A[0] ^ A[-1]))
	for (i, a) in enumerate(A):
		if a & k:
			break
	return 1 + max(dfs(A[:i]), dfs(A[i:]))
print(n - dfs(A))


import math

def num_to_remove(a):
	if len(a) == 0:
		return 0
	max_a = max(a)
	if max_a == 0:
		return len(a) - 1
	highest_bit = int(math.log2(max_a))
	cutoff = 2 ** highest_bit
	s_0 = []
	s_1 = []
	for a_i in a:
		if (a_i >> highest_bit) % 2:
			s_1.append(a_i ^ cutoff)
		else:
			s_0.append(a_i)
	if len(s_0) <= 1:
		return num_to_remove(s_1)
	elif len(s_1) == 1:
		return num_to_remove(s_0)
	else:
		assert len(s_0) > 1 and len(s_1) > 1
		return min(len(s_0) - 1 + num_to_remove(s_1), len(s_1) - 1 + num_to_remove(s_0))
n = int(input())
a = [int(i) for i in input().split()]
print(num_to_remove(a))


from sys import stdin
import sys

def solve(a):
	if len(a) <= 1:
		return len(a)
	lis = [[]]
	for i in range(len(a)):
		if i == 0 or a[i - 1].bit_length() == a[i].bit_length():
			if a[i] != 0:
				lis[-1].append(a[i] ^ 1 << a[i].bit_length() - 1)
			else:
				lis[-1].append(0)
		else:
			lis.append([])
			if a[i] != 0:
				lis[-1].append(a[i] ^ 1 << a[i].bit_length() - 1)
			else:
				lis[-1].append(0)
	ans = 0
	tmp = 0
	for i in range(len(lis)):
		if i == 0:
			ans = max(ans, len(lis) - 1 + solve(lis[0]))
		else:
			ans = max(ans, len(lis) - i + solve(lis[i]))
	return ans
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
a.sort()
print(n - solve(a))


import sys
input = sys.stdin.buffer.readline
n = int(input())
a = list(map(int, input().split()))
dp = {a[i]: 1 for i in range(n)}
for i in range(30):
	next = {}
	for val in dp:
		if not val >> 1 in next:
			next[val >> 1] = -dp[val]
		elif next[val >> 1] < 0:
			next[val >> 1] = max(-next[val >> 1], dp[val])
		else:
			next[val >> 1] = max(next[val >> 1], abs(dp[val]))
	dp = next
	for d in dp:
		if dp[d] > 0:
			dp[d] = dp[d] + 1
		else:
			dp[d] = -dp[d]
print(n - dp[0])


see = [1]
for i in range(41):
	see.append(see[-1] * 2)

def func(arr, num):
	if num == 0:
		return len(arr)
	if len(arr) == 1:
		return 1
	(arr1, arr2) = ([], [])
	for i in arr:
		if i ^ see[num] == i - see[num]:
			arr2.append(i)
		else:
			arr1.append(i)
	if len(arr1) == 0 or len(arr2) == 0:
		return func(arr, num - 1)
	return 1 + max(func(arr1, num - 1), func(arr2, num - 1))

def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(len(arr) - func(arr, 41))
t = 1
while t > 0:
	solve()
	t = t - 1


from math import log2

def dfs(a):
	if len(a) == 1:
		return 1
	mask = 1 << int(log2(a[0] ^ a[-1]))
	for (i, v) in enumerate(a):
		if v & mask:
			break
	return max(dfs(a[0:i]), dfs(a[i:len(a)])) + 1
n = int(input())
a = sorted(map(int, input().split()))
print(n - dfs(a))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if not True else 1):
	n = int(input())
	a = list(map(int, input().split()))

	def f(a, bit=32):
		if bit < 0:
			return 0
		(x, y) = ([], [])
		for each in a:
			if each & 1 << bit:
				x += [each]
			else:
				y += [each]
		if min(len(x), len(y)) == 0:
			return f(a, bit - 1)
		if min(len(x), len(y)) >= 2:
			return min(len(y) - 1 + f(x, bit - 1), len(x) - 1 + f(y, bit - 1))
		if len(x) == 1:
			x = list(y)
		return f(x, bit - 1)
	print(f(a))


def largest_good(a):
	if len(a) <= 3:
		return len(a)
	mx = max(a)
	cutoff = 1
	while 2 * cutoff <= mx:
		cutoff *= 2
	s0 = []
	s1 = []
	for i in a:
		if i >= cutoff:
			s1.append(i)
		else:
			s0.append(i)
	if s0 and s1:
		return 1 + max(largest_good(s0), largest_good(s1))
	else:
		s1 = [i - cutoff for i in s1]
		return largest_good(s1)
n = int(input())
a = [int(i) for i in input().split()]
print(n - largest_good(a))


import io, os
from math import *
n = int(input())
a = sorted([int(x) for x in input().split()])

def solve(l, bit):
	if len(l) <= 1:
		return 0
	if bit == 0:
		return 0
	high = [x ^ 1 << bit for x in l if x & 1 << bit]
	low = [x for x in l if not x & 1 << bit]
	sh = solve(high, bit - 1)
	sl = solve(low, bit - 1)
	if not low:
		return sh
	if not high:
		return sl
	return min(len(high) - 1 + sl, len(low) - 1 + sh)
print(solve(a, 40))


n = int(input())
a = list(map(int, input().split()))

def rec(s, i):
	if len(s) in (0, 1, 2):
		return len(s)
	mask = 1 << i
	a = []
	b = []
	for one in s:
		if one & mask:
			a.append(one)
		else:
			b.append(one)
	if not a or not b:
		return rec(s, i - 1)
	return 1 + max(rec(a, i - 1), rec(b, i - 1))
print(len(a) - rec(a, 31))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
(n, v) = (N(), RLL())
t = [0] * 30
for i in range(30):
	t[i] = 1 << i

def dfs(l, r, k, key):
	if l + 1 >= r:
		return 0
	p = key | t[k]
	a = l
	for b in range(l, r):
		if v[b] < p:
			(v[b], v[a]) = (v[a], v[b])
			a += 1
	return min(max(0, a - l - 1) + dfs(a, r, k - 1, p), max(0, r - a - 1) + dfs(l, a, k - 1, key))
print(dfs(0, n, 29, 0))


def main():
	n = int(input())
	a = [int(word) for word in input().rstrip().split()]
	x = max(a)
	arr = {}
	for num in a:
		arr[num] = 1
	ans = 0
	while True:
		x >>= 1
		dp = {}
		for i in arr:
			p = i >> 1
			if p not in dp:
				dp[p] = arr[i]
			else:
				dp[p] = max(dp[p] + 1, arr[i] + 1)
				ans = max(ans, dp[p])
		arr = dp
		if x == 0:
			break
	print(n - ans)
main()


import sys
input = sys.stdin.buffer.readline

def largest_good(a):
	if len(a) <= 3:
		return len(a)
	mx = max(a)
	cutoff = 1
	while 2 * cutoff <= mx:
		cutoff *= 2
	s0 = []
	s1 = []
	for i in a:
		if i < cutoff:
			s0.append(i)
		else:
			s1.append(i)
	if s0 and s1:
		return 1 + max(largest_good(s0), largest_good(s1))
	else:
		s1 = [i - cutoff for i in s1]
		return largest_good(s1)

def prog():
	n = int(input())
	a = list(map(int, input().split()))
	print(n - largest_good(a))
prog()


import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def costs(l, bit=32):
	if len(l) <= 2:
		return 0
	left = []
	right = []
	for el in l:
		if el & 1 << bit:
			left.append(el)
		else:
			right.append(el)
	return min(costs(left, bit - 1) + max(0, len(right) - 1), costs(right, bit - 1) + max(0, len(left) - 1))

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	print(costs(a))
t = 1
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 4)
n = int(input())
A = list(map(int, input().split()))

def calc(A):
	if len(A) == 1:
		return 1
	C = [[] for i in range(32)]
	for a in A:
		if a == 0:
			C[0].append(0)
		else:
			k = a.bit_length()
			C[a.bit_length()].append(a - (1 << k - 1))
	S = [0] * 32
	for i in range(30, -1, -1):
		if len(C[i]) != 0:
			S[i] = S[i + 1] + 1
		else:
			S[i] = S[i + 1]
	flag = 0
	ANS = 0
	for i in range(32):
		if C[i] == []:
			continue
		elif flag == 0:
			ANS = max(ANS, S[i + 1] + calc(C[i]))
			flag = 1
		else:
			ANS = max(ANS, S[i + 1] + calc(C[i]) + 1)
	return ANS
print(n - calc(A))


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
data = [None, None, 0]
N = int(input())
A = list(map(int, input().split()))
for a in A:
	dat = data
	for i in range(29, -1, -1):
		dat[2] += 1
		bit = a >> i & 1
		if dat[bit] is None:
			dat[bit] = [None, None, 0]
		dat = dat[bit]
	dat[2] += 1
ans = 1 << 60
for a in A:
	dat = data
	cnt = 0
	for i in range(29, -1, -1):
		bit = a >> i & 1
		n = dat[2]
		dat = dat[bit]
		n -= dat[2]
		if n >= 2:
			cnt += n - 1
	if ans > cnt:
		ans = cnt
print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()
from collections import defaultdict
n = II()
aa = LI()

def size(aa):
	if len(aa) == 1:
		return 1
	sa = defaultdict(list)
	for a in aa:
		sa[a.bit_length()].append(a)
	cc = []
	for (i, (s, A)) in enumerate(sorted(sa.items())):
		if len(A) == 1:
			cc.append(1)
			continue
		naa = []
		for a in A:
			naa.append(a ^ 1 << s - 1)
		cc.append(size(tuple(naa)))
	mx = 0
	for (i, c) in enumerate(cc):
		cur = len(cc) - i - 1 + c + 1
		if i == 0:
			cur -= 1
		if cur > mx:
			mx = cur
	return mx
ans = n - size(aa)
print(ans)


import sys
try:
	(sys.stdin, sys.stdout) = (open('in.txt', 'r'), open('out.txt', 'w'))
except:
	pass
ii1 = lambda : int(sys.stdin.readline().strip())
is1 = lambda : sys.stdin.readline().strip()
iia = lambda : list(map(int, sys.stdin.readline().strip().split()))
isa = lambda : sys.stdin.readline().strip().split()
mod = int(1000000000.0 + 7)
from collections import *
from math import *
n = ii1()
arr = iia()
arr.sort()

def dfs(arr):
	if len(arr) == 1:
		return 1
	k = 1 << int(log2(arr[0] ^ arr[-1]))
	for (i, a) in enumerate(arr):
		if a & k:
			break
	return 1 + max(dfs(arr[:i]), dfs(arr[i:]))
print(n - dfs(arr))


import sys
input = sys.stdin.readline

def fmax(a):
	if len(a) <= 2:
		return len(a)
	l = []
	i = 1
	cur = -1
	ind = 0
	if a[0] == 0:
		l.append([0])
		ind += 1
		cur = 0
	while ind < len(a):
		if a[ind] < i:
			l[cur].append(a[ind] - i // 2)
		else:
			cur += 1
			while a[ind] >= i:
				i *= 2
			l.append([a[ind] - i // 2])
		ind += 1
	if cur == 0:
		return fmax(l[0])
	mx = 0
	m = len(l)
	for i in range(m):
		mx = max(mx, fmax(l[i]) + m - i)
		if i == 0:
			mx -= 1
	return mx
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(n - fmax(a))


n = int(input())
a = sorted([int(x) for x in input().split()])

def solve(l, bit):
	if len(l) <= 1:
		return 0
	if bit == 0:
		return 0
	high = [x ^ 1 << bit for x in l if x & 1 << bit]
	low = [x for x in l if not x & 1 << bit]
	sh = solve(high, bit - 1)
	sl = solve(low, bit - 1)
	if not low:
		return sh
	if not high:
		return sl
	return min(len(high) - 1 + sl, len(low) - 1 + sh)
print(solve(a, 40))


import sys
from collections import defaultdict
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
N = int(input())
arr = list(map(int, input().split()))
max_val = max(arr)
max_binary_len = len(bin(max_val)) - 2

class Node:

	def __init__(self):
		self.zero = None
		self.one = None
		self.end = False
root = Node()
for v in arr:
	cur = root
	ln = max_binary_len - 1
	while ln >= 0:
		msb = v & 1 << ln > 0
		if msb:
			if cur.one is None:
				cur.one = Node()
			cur = cur.one
		else:
			if cur.zero is None:
				cur.zero = Node()
			cur = cur.zero
		ln -= 1
	cur.end = 1

def rec(cur):
	if not cur:
		return 0
	if cur.end:
		return cur.end
	left = rec(cur.zero)
	right = rec(cur.one)
	if left > 1 and right > 1:
		return 1 + max(left, right)
	return left + right
valid = rec(root)
print(N - valid)


from bisect import bisect_left
import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
tmp = 0
t = bisect_left(a, 0)
s = bisect_left(a, 1 << 31)
stack = [(0, 1 << 31, t, s, 0)]
while stack:
	(l, r, l1, r1, score) = stack.pop()
	ans = max(score, ans)
	if l + 1 == r:
		ans = max(score + 1, ans)
	elif l < r:
		c = bisect_left(a, (l + r) // 2)
		if c == l1 and r1 != c:
			stack.append(((l + r) // 2, r, c, r1, score))
		elif c != l1 and r1 == c:
			stack.append((l, (l + r) // 2, l1, c, score))
		elif c != l1 and r1 != c:
			stack.append((l, (l + r) // 2, l1, c, score + 1))
			stack.append(((l + r) // 2, r, c, r1, score + 1))
print(n - ans)