You are given a sequence of integers a_{1},a_{2},a_{3}.....a_{n}. You are free to replace any integer with any other positive integer. How many integers must be replaced to make the resulting sequence strictly increasing? 

Input Format 

The first line of the test case contains an integer $N$ - the number of entries in the sequence. 

The next line contains $N$ space separated integers where the $i^{\mbox{th}}$ integer is $a_i$.

Output Format 

Output the minimal number of integers that should be replaced to make the sequence strictly increasing.

Constraints 

$0<N\leq10^6$ 

$0<a_i\leq10^9$  

Sample Input #00

3
4 10 20

Sample Output #00

0

Sample Input #01

6
1 7 10 2 20 22

Sample Output #01

1

Sample Input #02

5
1 2 2 3 4 

Sample Output #02

3

Explanation 

In the first sample input, we need not replace anything, hence the output is 0. 

In the second sample input, we can replace 2 with any integer between 11 and 19 to make the sequence strictly increasing, hence the output is 1. 

In the third sample input, we can obtain 1, 2, 3, 4, 5 by changing the last three elements of the sequence.

Difficulty: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(X):
	N = len(X)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if X[i] < i + 1:
			continue
		if X[i] >= X[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if X[M[mid]] <= X[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
X = [int(a) for a in number_string]
L = longest_propper_subsequence(X)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(X):
	N = len(X)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if X[i] < i + 1:
			continue
		if X[i] >= X[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if X[M[mid]] <= X[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
X = [int(a) for a in number_string]
L = longest_propper_subsequence(X)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


import bisect
n = int(input())
a = [-99] * 100
c = 100
for i in map(lambda x: int(x), input().split()):
	a.append(i - c)
	c += 1
l = a[:1]
for i in a[1:]:
	j = bisect.bisect(l, i)
	if j != len(l):
		l[j] = i
	else:
		l.append(i)
print(100 + n - len(l))


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import math
import os
import random
import re
import sys
import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def p(seq):
	for i in range(len(seq)):
		seq[i] -= i

def f(array):
	g = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(g, array[x])
		if i != len(g):
			g[i] = array[x]
		else:
			g.append(array[x])
	return len(g)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	p(array)
	print(n - f(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def a(seq):
	for i in range(len(seq)):
		seq[i] -= i

def p(array):
	g = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(g, array[x])
		if i != len(g):
			g[i] = array[x]
		else:
			g.append(array[x])
	return len(g)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	a(array)
	print(n - p(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


Y_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	Y = len(arr)
	M = (Y + 1) * [0]
	Z = 0
	for i in range(0, Y):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[Z]] + i - M[Z]:
			j = Z + 1
		else:
			lower = 1
			upper = Z
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > Z:
			Z = j
	return Z
arr = [int(a) for a in number_string]
Z = longest_propper_subsequence(arr)
print(Y_0 - Z)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


import bisect

def parse(seq):
	for i in range(len(seq)):
		seq[i] -= i

def patience_sort(array):
	piles = [array[0]]
	for x in range(1, len(array)):
		i = bisect.bisect_right(piles, array[x])
		if i != len(piles):
			piles[i] = array[x]
		else:
			piles.append(array[x])
	return len(piles)

def main():
	n = int(input())
	array = [i for i in range(-99, 1)] + list(map(int, input().split()))
	parse(array)
	print(n - patience_sort(array) + 100)
main()


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)


N_0 = int(input())
number_string = input().split()

def longest_propper_subsequence(arr):
	N = len(arr)
	M = (N + 1) * [0]
	L = 0
	for i in range(0, N):
		if arr[i] < i + 1:
			continue
		if arr[i] >= arr[M[L]] + i - M[L]:
			j = L + 1
		else:
			lower = 1
			upper = L
			while lower <= upper:
				mid = int((upper + lower) / 2)
				if arr[M[mid]] <= arr[i] - i + M[mid]:
					lower = mid + 1
				else:
					upper = mid - 1
			j = lower
		M[j] = i
		if j > L:
			L = j
	return L
arr = [int(a) for a in number_string]
L = longest_propper_subsequence(arr)
print(N_0 - L)