Most problems on CodeChef highlight chef's love for food and cooking but little is known about his love for racing sports. He is an avid Formula 1 fan. He went to watch this year's Indian Grand Prix at New Delhi. He noticed that one segment of the circuit was a long straight road. It was impossible for a car to overtake other cars on this segment. Therefore, a car had to lower down its speed if there was a slower car in front of it. While watching the race, Chef started to wonder how many cars were moving at their maximum speed.
Formally, you're given the maximum speed of N cars in the order they entered the long straight segment of the circuit. Each car prefers to move at its maximum speed. If that's not possible because of the front car being slow, it might have to lower its speed. It still moves at the fastest possible speed while avoiding any collisions. For the purpose of this problem, you can assume that the straight segment is infinitely long.
Count the number of cars which were moving at their maximum speed on the straight segment.

-----Input-----
The first line of the input contains a single integer T denoting the number of test cases to follow. Description of each test case contains 2 lines. The first of these lines contain a single integer N, the number of cars. The second line contains N space separated integers, denoting the maximum speed of the cars in the order they entered the long straight segment.

-----Output-----
For each test case, output a single line containing the number of cars which were moving at their maximum speed on the segment.

-----Example-----
Input:
3
1
10
3
8 3 6
5
4 5 1 2 3

Output:
1
2
2

-----Constraints-----

1 ≤ T ≤ 100

1 ≤ N ≤ 10,000

All speeds are distinct positive integers that fit in a 32 bit signed integer.

Each input file will not be larger than 4 MB (4,000,000,000 bytes) in size.

WARNING! The input files are very large. Use faster I/O.

Difficulty: EASY
Tags: Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
while t:
	n = int(input())
	arr = [int(x) for x in input().split()]
	cnt = 1
	min_sp = arr[0]
	for i in range(1, n):
		if min_sp > arr[i]:
			min_sp = min(min_sp, arr[i])
			cnt = cnt + 1
	print(cnt)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	max_speed = list(map(int, input().split(' ')))
	if n == 1:
		print(1)
	else:
		count = 1
		m = max_speed[0]
		for i in range(1, n):
			if max_speed[i] <= m:
				m = max_speed[i]
				count += 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))
	count = 1
	x = a[0]
	for i in range(1, n):
		if a[i] <= x:
			count += 1
			x = a[i]
		else:
			count += 0
	print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	min_a = l[0]
	c_out = 1
	for j in range(1, n):
		if min_a >= l[j]:
			c_out += 1
			min_a = l[j]
	print(c_out)


p = int(input())
for i in range(p):
	h = int(input())
	a = list(map(int, input().split()))
	c = 1
	m = a[0]
	for i in range(1, h):
		if m >= a[i]:
			c = c + 1
		m = min(m, a[i])
	print(c)


for i in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	st = l[0]
	cnt = 1
	for i in range(1, len(l)):
		if l[i] < st:
			cnt = cnt + 1
			st = l[i]
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 1
	m = l[0]
	for i in range(1, n):
		if l[i] <= m:
			c += 1
			m = l[i]
	print(c)


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


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


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = 1
	m = a[0]
	for j in range(1, n):
		if a[j] <= m:
			c += 1
			m = a[j]
	print(c)


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
t = int(input())
for _ in range(t):
	n = int(input())
	cars = get_ints()
	counter = 1
	if n == 1:
		print(1)
	else:
		min = cars[0]
		for i in range(1, n):
			if cars[i] <= min:
				counter += 1
				min = cars[i]
		print(counter)


T = int(input())
for _ in range(T):
	N = int(input())
	l = list(map(int, input().split()))
	C = 0
	min1 = l[0]
	for i in range(N):
		if l[i] <= min1:
			min1 = min(min1, l[i])
			C = C + 1
	print(C)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	ans = 0
	Min = arr[0]
	for i in range(n):
		if arr[i] <= Min:
			Min = min(Min, arr[i])
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	min = a[0]
	count = 0
	for i in range(0, n):
		if a[i] <= min:
			count = count + 1
			min = a[i]
		else:
			pass
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if arr[i - 1] < arr[i]:
			arr[i] = arr[i - 1]
		else:
			ans += 1
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	arr = [int(ele) for ele in input().split()]
	smallAns = 1
	minSpeed = arr[0]
	for i in range(1, N):
		if arr[i] <= minSpeed:
			smallAns += 1
			minSpeed = arr[i]
	print(smallAns)


for tc in range(int(input())):
	n = int(input())
	v = list(map(int, input().split()))
	cars_at_max_speed = 0
	cars_in_front_speed = 1e+20
	for i in range(n):
		if v[i] < cars_in_front_speed:
			cars_at_max_speed += 1
			cars_in_front_speed = v[i]
	print(cars_at_max_speed)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	k = n
	for i in range(1, n):
		if a[i - 1] < a[i]:
			a[i] = a[i - 1]
			k = k - 1
	print(k)


for t in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	count = 1
	for i in range(n - 1):
		if lis[i] > lis[i + 1]:
			count += 1
		else:
			lis[i + 1] = lis[i]
	print(count)


import sys
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	minn = sys.maxsize
	for i in range(n):
		if l[i] < minn:
			minn = l[i]
			c += 1
	print(c)


for x in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 1
	t = l[0]
	for y in range(1, n):
		if l[y] <= t:
			c += 1
			t = l[y]
	print(c)


t = int(input())
for i in range(t):
	k = 0
	n = int(input())
	l = list(map(int, input().split()))
	max = l[0]
	for j in range(n):
		if l[j] <= max:
			k = k + 1
			max = l[j]
	print(k)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	(cnt, prev) = (0, lst[0])
	for ele in lst:
		if ele <= prev:
			cnt += 1
			prev = ele
	print(cnt)


for i in range(int(input(''))):
	x = int(input(''))
	p = [int(x) for x in input('').split()]
	k = list(p)
	c = 0
	d = k[0]
	for j in k:
		if j <= d:
			c = c + 1
			d = j
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	mini = l[0]
	for i in range(0, n):
		if l[i] <= mini:
			mini = l[i]
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
	else:
		l = ['n']
		v = 1
		for i in range(1, n):
			if a[i - 1] >= a[i]:
				l.append('n')
			else:
				a[i] = a[i - 1]
				l.append('c')
		print(l.count('n'))


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


for i in range(int(input())):
	x = int(input())
	list = input().split()
	list = [eval(i) for i in list]
	yas = list[0]
	count = 1
	for i in range(1, len(list)):
		if list[i] < yas:
			count += 1
			yas = list[i]
	print(count)


for _ in range(int(input())):
	n = int(input())
	cars = 1
	l = list(map(int, input().split()))
	for i in range(1, len(l)):
		if l[i] <= l[i - 1]:
			cars += 1
		else:
			l[i] = l[i - 1]
	print(cars)


for j in range(int(input())):
	x = int(input())
	list = input().split()
	list = [eval(i) for i in list]
	small = list[0]
	count = 1
	for i in range(1, len(list)):
		if list[i] < small:
			count += 1
			small = list[i]
	print(count)


T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	for j in range(len(A) - 1):
		if A[j] < A[j + 1]:
			A[j + 1] = A[j]
	print(len(set(A)))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ct = 1
	for i in range(n - 1):
		if l[i] < l[i + 1]:
			l[i + 1] = l[i]
		else:
			ct += 1
	print(ct)


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


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	lowest = s[0]
	fastest = 1
	for i in range(1, n):
		if s[i] <= lowest:
			fastest += 1
			lowest = s[i]
	print(fastest)


for t in range(int(input())):
	N = int(input())
	C = list(map(int, input().split()))
	count = 1
	fast = C[0]
	for c in range(1, len(C)):
		if C[c] <= fast:
			count += 1
			fast = C[c]
	print(count)


t_cases = int(input())
for i in range(t_cases):
	n_cars = int(input())
	max_speeds = list(map(int, input().split()))
	res = 0
	for j in range(n_cars - 1):
		if max_speeds[j + 1] > max_speeds[j]:
			max_speeds[j + 1] = max_speeds[j]
			res += 1
	print(n_cars - res)


def race(speed):
	ms = None
	c = 1
	for i in speed:
		if ms == None:
			ms = i
		elif i < ms:
			ms = i
			c = c + 1
	return c
for i in range(int(input())):
	n = int(input())
	speed = list(map(int, input().split()))
	print(race(speed))


for _ in range(int(input())):
	n = int(input())
	l = [int(item) for item in input().split(maxsplit=n)[:n]]
	count = 1
	mini = l[0]
	if n == 1:
		print(1)
	else:
		for i in range(1, n):
			if l[i] <= mini:
				mini = l[i]
				count = count + 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	m = [int(i) for i in input().split()]
	if n == 1:
		print(1)
	else:
		x = 1
		for i in range(n - 1):
			if m[i] >= m[i + 1]:
				x = x + 1
			else:
				m[i + 1] = m[i]
		print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(i) for i in input().split()]
	x = []
	c = 0
	for i in range(n):
		x.append(s[i])
	for i in range(n - 1):
		if x[i] < x[i + 1]:
			x[i + 1] = x[i]
	for i in range(n):
		if s[i] == x[i]:
			c += 1
	print(c)


T = int(input())
for _ in range(T):
	N = int(input())
	cars = list(map(int, input().split()))
	ans = 0
	for i in range(len(cars)):
		if i == 0:
			ans += 1
		elif cars[i - 1] < cars[i]:
			cars[i] = cars[i - 1]
		else:
			ans += 1
	print(ans)


T = int(input())
for i in range(T):
	C = 1
	A = int(input())
	B = list(map(int, input().split()))
	s = B[0]
	if A == 1:
		print(1)
	else:
		for i in range(1, A):
			if s >= B[i]:
				s = B[i]
				C = C + 1
		print(C)


t = int(input())
while t > 0:
	x = int(input())
	l = list(map(int, input().split()))
	count = 1
	if len(l) == 1:
		print(1)
		t -= 1
		continue
	else:
		for i in range(len(l) - 1):
			if l[i] > l[i + 1]:
				count += 1
			else:
				l[i + 1] -= l[i + 1] - l[i]
	print(count)
	t -= 1


test = int(input())
for i in range(test):
	no_cars = int(input())
	L = [int(x) for x in input().split()]
	cars_fast = 1
	for j in range(no_cars - 1):
		if L[j] >= L[j + 1]:
			cars_fast = cars_fast + 1
		else:
			L[j + 1] = L[j]
	print(cars_fast)


for T in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))[:n]
	cnt = 1
	for i in range(1, n):
		if li[i] - li[i - 1] < 0:
			cnt += 1
		else:
			li[i] = li[i - 1]
	print(cnt)


t = int(input())
for i in range(0, t):
	n = int(input())
	speed = []
	speed = list(map(int, input().split()))
	count = 0
	max_speed = speed[0]
	for move in speed:
		if move <= max_speed:
			count += 1
			max_speed = move
	print(count)


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


for _ in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	if n == 1:
		print(1)
	elif n == 0:
		print(0)
	else:
		mi = m[0]
		count = 0
		for i in range(1, n):
			mi = min(m[i], mi)
			if m[i] <= mi:
				count += 1
		print(count + 1)


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


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split(' ')))
	max_speed = l[0]
	ctr = 0
	for j in range(n):
		if l[j] > max_speed:
			continue
		else:
			max_speed = l[j]
			ctr += 1
	print(ctr)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	l1 = l[0]
	for i in range(1, n):
		if l[i] <= l1:
			l1 = l[i]
			ans = ans + 1
	print(ans)


T = int(input())
for i in range(T):
	N = int(input())
	maxSpeeds = list(map(int, input().split()))
	travSpeeds = []
	for j in range(N):
		travSpeeds.append(maxSpeeds[j])
	for j in range(N - 1):
		if travSpeeds[j] < travSpeeds[j + 1]:
			travSpeeds[j + 1] = travSpeeds[j]
	maxSpeedCars = 0
	for j in range(N):
		if travSpeeds[j] == maxSpeeds[j]:
			maxSpeedCars += 1
	print(maxSpeedCars)


t = int(input())
for i in range(t):
	n = int(input())
	speeds = list(map(int, input().split()))
	stack = [speeds[0]]
	count = 1
	for j in range(1, n):
		while stack and speeds[j] <= stack[-1]:
			stack.pop()
		stack.append(speeds[j])
		count += len(stack) == 1
	print(count)


def maxSpeed(arr, l):
	count = 0
	Min = 10000000000000
	for i in arr:
		if i < Min:
			Min = i
			count += 1
	return count
t = int(input())
for i in range(t):
	l = int(input())
	arr = list(map(int, input().split()))
	print(maxSpeed(arr, l))


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = []
	s.append(a[0])
	for i in range(1, n):
		if a[i] >= s[i - 1]:
			s.append(s[i - 1])
		else:
			s.append(a[i])
	count = 0
	for i in range(n):
		if s[i] == a[i]:
			count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	min1 = l[0]
	for i in range(n):
		if l[i] <= min1:
			min1 = min(min1, l[i])
			c = c + 1
	print(c)


i = int(input())
for _ in range(i):
	a = int(input())
	b = list(map(int, input().split()))
	q = 0
	p = b[0]
	for t in b:
		if t <= p:
			q += 1
			p = t
	print(q)


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


for i in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	r = 1
	for i in range(1, n):
		if l[i] <= l[i - 1]:
			r += 1
		else:
			l[i] = l[i - 1]
	print(r)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 1
	if n == 1:
		print(1)
	else:
		for i in range(0, n - 1):
			if l[i] >= l[i + 1]:
				count += 1
			else:
				l[i + 1] = l[i]
		print(count)


t = int(input())
for i in range(t):
	n = int(input())
	car_speed = list(map(int, input().split()[:n]))
	max_speed = car_speed[0]
	c = 1
	for x in range(1, n):
		if car_speed[x] < max_speed:
			max_speed = car_speed[x]
			c += 1
		else:
			car_speed[x] = max_speed
	print(c)


for i in range(int(input())):
	ans = 0
	n = int(input())
	a = [*map(int, input().split())]
	k = 10 ** 18
	for i in range(n):
		if a[i] <= k:
			ans += 1
		k = min(k, a[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	max_speed = a[0]
	ans = 1
	for i in range(1, n):
		if a[i] <= max_speed:
			ans += 1
			max_speed = a[i]
	print(ans)


input_1 = int(input())
for i in range(input_1):
	input_2 = int(input())
	arr = list(map(int, input().split()))
	count = 1
	mini = arr[0]
	if input_2 == 1:
		print(count)
	else:
		for j in range(1, input_2):
			if arr[j] <= mini:
				mini = arr[j]
				count = count + 1
		print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	count = 1
	if len(l) == 1:
		print(1)
		continue
	for i in range(1, len(l)):
		if l[i] < l[i - 1]:
			count += 1
		elif l[i - 1] < l[i]:
			l[i] = l[i - 1]
	print(count)


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


t = int(input())
for i in range(t):
	n = int(input())
	l1 = list(map(int, input().split()))
	curr = l1[0]
	ans = 0
	for j in range(n):
		if l1[j] <= curr:
			ans += 1
			curr = l1[j]
	print(ans)


T = int(input())
for i in range(T):
	n = int(input())
	lst = list(map(int, input().split()))
	count = 1
	swap = lst[0]
	for i in range(n - 1):
		if lst[i + 1] < swap:
			count += 1
			swap = lst[i + 1]
		else:
			continue
	print(count)


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	c = 1
	for i in range(n - 1):
		if m[i] < m[i + 1]:
			m[i + 1] = m[i]
		else:
			c += 1
	print((c, '1')[n == 1])


t = int(input())
while t != 0:
	n = int(input())
	arr = list(map(int, input().strip().split()))
	count = 1
	min = arr[0]
	for i in range(1, len(arr)):
		if arr[i] <= min:
			count = count + 1
		if arr[i] < min:
			min = arr[i]
	print(count)
	t = t - 1


T = int(input())
for _ in range(T):
	N = int(input())
	S = list(map(int, input().split()))
	max_s = S[0]
	cars_max = 1
	for s in range(1, N):
		if S[s] <= max_s:
			cars_max += 1
			max_s = S[s]
	print(cars_max)


n = int(input())
for i in range(n):
	a = int(input())
	l = [int(x) for x in input().split()]
	m = l[0]
	c = 1
	for i in range(1, a):
		if m >= l[i]:
			c += 1
			m = l[i]
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	hello = list(map(int, input().strip().split()))
	count = 0
	for i in range(len(hello) - 1):
		if hello[i + 1] > hello[i]:
			hello[i + 1] = hello[i]
			count = count + 1
	print(n - count)


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	s = set()
	s.add(m[0])
	for i in range(n - 1):
		if m[i] < m[i + 1]:
			s.add(m[i])
			m[i + 1] = m[i]
		else:
			s.add(m[i + 1])
	print(len(s))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(1, n):
		if arr[i] <= arr[i - 1]:
			count += 1
		else:
			arr[i] = arr[i - 1]
	print(count + 1)


for _ in range(int(input())):
	i = int(input())
	cars = list(map(int, input().split()))
	ans = 1
	if i == 1:
		print(ans)
	else:
		for val in range(1, i):
			if cars[val] <= cars[val - 1]:
				ans += 1
			else:
				cars[val] = cars[val - 1]
		print(ans)


for i in range(int(input())):
	x = int(input())
	m = [int(i) for i in input().split()]
	f = 0
	for i in range(1, x):
		if m[i] <= m[i - 1]:
			f = f + 1
		else:
			m[i] = m[i - 1]
	print(len(set(m)))


t = int(input())
for i in range(t):
	n = int(input())
	max_speeds = list(map(int, input().split()))
	ans = 0
	for j in range(1, len(max_speeds)):
		if max_speeds[j] > max_speeds[j - 1]:
			max_speeds[j] = max_speeds[j - 1]
		else:
			ans += 1
	print(ans + 1)


for _testcase in range(int(input())):
	x = input()
	a = list(map(int, input().split()))
	y = a[0]
	count = 0
	for i in a:
		if i <= y:
			count += 1
			y = i
	print(count)


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


for _ in range(int(input())):
	N = int(input())
	x = list(map(int, input().split()))
	i = 0
	c = 1
	xx = [x[0]]
	for i in x[1:]:
		if i > xx[-1]:
			xx.append(xx[-1])
		else:
			xx.append(i)
			c += 1
	print(c)


t = int(input())
for t in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	counter = 0
	current = a[0]
	for i in range(0, len(a)):
		if a[i] <= current:
			counter = counter + 1
			current = a[i]
	print(counter)


t = int(input())
l = []
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(n - 1):
		if a[j] <= a[j + 1]:
			a[j + 1] = a[j]
			count += 1
	l.append(n - count)
for i in l:
	print(i)


for t in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	ans = [1]
	if n == 1:
		print(1)
	else:
		for i in range(1, n):
			if s[i - 1] >= s[i]:
				ans.append(1)
			else:
				s[i] = s[i - 1]
		print(len(ans))