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.

Source: codechef | Difficulty: EASY
Tags: Constructive algorithms

Data structures

Ad-hoc


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))