wonderful-sequence

A sequence of integers is called a wonderful sequence if all the integers in it are positive and it is a strictly increasing sequence.

Given a sequence of integers, you have to make it a wonderful sequence. For that you can change any element you want, but you should make as less changes as possible in order to make it a wonderful sequence.

Input

The first line of input is an integer T(T ≤ 5), the number of test cases. Each test case contains 2 lines.

The first line of the test case contains an integer (0 < N ≤ 100000), i.e. the number of elements in the original sequence.

The second line contains N positive integers, no larger than 2000000000, which forms the original sequence.

Output

For each test case output the minimal number of elements you must change in the original sequence to make it a wonderful sequence.

SAMPLE INPUT
3
2
1 2
3
3 2 1
5
10 5 6 7 8

SAMPLE OUTPUT
0
2
1

Explanation

For the 1st test case you needn't to change any elements.
For the 2nd test case you can change 3 into 1 and change 1 into 3.
For the 3rd test case you can change 10 into 1.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input())
while t>0:
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = 0
	if arr[0]>arr[1]:
		arr[0]= arr[1]-1
		count+=1
	if arr[0]<0:
		arr[0] = 1
		count+=1
	
	
	for i in range(1,n):
		if arr[i]<=arr[i-1]:
			arr[i] = arr[i-1]+1
			count+=1
	print(count)	
	t-=1


for i in range(eval(input())):
	n=eval(input())
	c=0
	a=list(map(int,input().split()))
	for j in range(n-1):
		if(a[j]>=a[j+1]):
			c=c+1
	print(c)		


for i in range(eval(input())):
	n=eval(input())
	c=0
	a=list(map(int,input().split()))
	for j in range(n-1):
		if(a[j]<a[j+1]):
			j+=1
		else:
			c=c+1
			j+=1
	print(c)		
			


for i in range(eval(input())):
	n=eval(input())
	c=0
	a=list(map(int,input().split()))
	for j in range(n-1):
		if(a[j]<a[j+1]):
			j+=1
		else:
			c=c+1
			j+=1
	print(c)		
			


from sys import stdin
def subsequence(seq):
	if not seq:
		return seq
 
	M = [None] * len(seq)    
	P = [None] * len(seq)
 
   
	L = 1
	M[0] = 0
 
	
	for i in range(1, len(seq)):
	   
		lower = 0
		upper = L
 
	   
		if seq[M[upper-1]] < seq[i]:
			j = upper
 
		else:
		   
			while upper - lower > 1:
				mid = (upper + lower) // 2
				if seq[M[mid-1]] < seq[i]:
					lower = mid
				else:
					upper = mid
 
			j = lower    
 
		P[i] = M[j-1]
 
		if j == L or seq[i] < seq[M[j]]:
			M[j] = i
			L = max(L, j+1)
 
	
	result = []
	pos = M[L-1]
	for _ in range(L):
		result.append(seq[pos])
		pos = P[pos]
 
	return result[::-1]
t = stdin.readline()
t = int(t)
for jj in range(t):
	n = int(stdin.readline())
	a = list(map(int,stdin.readline().strip().split()))
	b =  subsequence(a)
	print(n - len(b))


n=int(input())
for j in range(n):
	n=int(input())
	swap=0
	s=list(map(int,input().split()))
	i=0
	while i<n:
		if s[i]>min(s[i:]) and min(s[i:])==1:
			s[i]=1
			swap+=1
		elif s[i]>min(s[i:]) and min(s[i:])!=1:
			s[i]=min(s[i:])-1
			swap+=1
			
		i+=1
	if len(set(s))==1:
		print(len(s)-1)
	else:
		print(swap)