Chef wants to buy a new phone, but he is not willing to spend a lot of money. Instead, he checks the price of his chosen model everyday and waits for the price to drop to an acceptable value. So far, he has observed the price for $N$ days (numbere $1$ through $N$); for each valid $i$, the price on the $i$-th day was $P_i$ dollars.
On each day, Chef considers the price of the phone to be good if it is strictly smaller than all the prices he has observed during the previous five days. If there is no record of the price on some of the previous five days (because Chef has not started checking the price on that day yet), then Chef simply ignores that previous day ― we could say that he considers the price on that day to be infinite.
Now, Chef is wondering ― on how many days has he considered the price to be good? Find the number of these days.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $P_1, P_2, \dots, P_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of days with a good price.

-----Constraints-----
- $1 \le T \le 100$
- $7 \le N \le 100$
- $350 \le P_i \le 750$ for each valid $i$

-----Subtasks-----
Subtask #1 (30 points): $N = 7$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
7
375 750 723 662 647 656 619

-----Example Output-----
2

-----Explanation-----
Example case 1: Chef considers the price to be good on day $1$, because he has not observed any prices on the previous days. The prices on days $2, 3, 4, 5, 6$ are not considered good because they are greater than the price on day $1$. Finally, the price on day $7$ is considered good because it is smaller than all of the prices on days $2, 3, 4, 5, 6$.

Source: codechef | Difficulty: EASY
Tags: Data structures

Implementation


Solutions:
def get_Min(l, i):
	mx = 10000000
	for j in range(i - 5, i):
		mx = min(mx, l[j])
	return mx
t = int(input())
for ni in range(t):
	n = int(input())
	l = [int(i) for i in input().split()]
	c = 1
	small = l[0]
	for i in range(1, 5):
		if l[i] < small:
			small = l[i]
			c = c + 1
	for i in range(5, n):
		if l[i] < get_Min(l, i):
			c = c + 1
	print(c)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	c = 1
	x = l[0]
	for i in range(1, n):
		if x == l[max(i - 6, 0)]:
			x = min(l[max(0, i - 5):i])
		else:
			x = min(l[i - 1], x)
		if l[i] < x:
			c += 1
	print(c)
	t -= 1


def prices(n, p):
	c = 0
	for i in range(n):
		if i == 0:
			c += 1
		elif i < 6:
			if p[i] < min(p[:i]):
				c += 1
		elif p[i] < min(p[i - 5:i]):
			c += 1
	return c
t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	print(prices(n, p))


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))[:n]
	c = 1
	for i in range(1, n):
		if i <= 5:
			if p[i] < min(p[:i]):
				c += 1
		elif p[i] < min(p[i - 5:i]):
			c += 1
	print(c)


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


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


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	good = 0
	last5 = [751] * 5
	for v in p:
		if v < min(last5):
			good += 1
		last5 = last5[1:] + [v]
	print(good)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	day = 1
	for i in range(1, n):
		if i <= 5:
			if a[i] < min(a[:i]):
				day += 1
		elif a[i] < min(a[i - 5:i]):
			day += 1
	print(day)


for i in range(int(input())):
	n = int(input())
	li = list(map(int, input().split()))
	count = 1
	for i in range(1, n):
		if i < 5:
			if min(li[:i]) > li[i]:
				count += 1
		elif min(li[i - 5:i]) > li[i]:
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	cnt = 1
	for i in range(1, n):
		r = i
		if i < 5:
			if min(lst[:i]) > lst[i]:
				cnt += 1
		elif min(lst[i - 5:i]) > lst[i]:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	c = 0
	mprcs = 5 * [751] + list(map(int, input().split()))
	for k in range(5, len(mprcs)):
		if min(mprcs[k - 5:k]) > mprcs[k]:
			c = c + 1
	print(c)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	count = 1
	for i in range(1, n):
		li = []
		for j in range(6):
			if i - j < 0:
				break
			else:
				li.append(l[i - j])
		li.sort()
		if l[i] == li[0] and li[0] != li[1]:
			count += 1
	print(count)


T = int(input())
for i in range(T):
	count = 1
	N = int(input())
	k = list(map(int, input().split()))
	min1 = k[0]
	for i in range(1, 6):
		if k[i] < min1:
			min1 = k[i]
			count += 1
	for i in range(6, N):
		if k[i - 6] == min1:
			value = None
			min1 = k[i - 5]
			for j in range(i - 4, i + 1):
				if k[j] < min1:
					min1 = k[j]
					value = j
			if i == value:
				count += 1
		elif k[i] < min1:
			min1 = k[i]
			count += 1
	print(count)


for tc in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	days5 = [1000]
	gdcnt = 0
	for i in p:
		if i < min(days5):
			gdcnt += 1
		if len(days5) == 5:
			days5.append(i)
			days5.pop(0)
		else:
			days5.append(i)
	print(gdcnt)


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


T = int(input())
for j in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.reverse()
	c = 1
	for i in range(N):
		B = A[i + 1:i + 6]
		if len(B) == 0:
			break
		elif A[i] < min(B):
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = l[::-1]
	c = 1
	for i in range(n):
		d = l[i + 1:i + 6]
		if len(d) == 0:
			break
		elif l[i] < min(d):
			c = c + 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = [751] * 5 + arr
	ans = 0
	for i in range(5, n + 5):
		if min(arr[i - 5:i]) > arr[i]:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = 1
	for j in range(1, n):
		if j - 5 < 0:
			mi = min(a[0:j])
			if mi > a[j]:
				g = g + 1
		else:
			mi = min(a[j - 5:j])
			if mi > a[j]:
				g = g + 1
	print(g)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = tuple(map(int, sys.stdin.readline().split()))
	r = 0
	t = 5 * [751]
	for i in range(n):
		if a[i] < min(t):
			r += 1
		t = t[1:] + [a[i]]
	print(r)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a = a[::-1]
	c = 1
	for i in range(n):
		b = a[i + 1:i + 6]
		if len(b) == 0:
			break
		elif a[i] < min(b):
			c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	c = 1
	for i in range(1, n):
		if i < 5:
			if min(arr[:i]) > arr[i]:
				c += 1
		elif min(arr[i - 5:i]) > arr[i]:
			c += 1
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split(' ')))
	count = 0
	for j in range(n):
		if j == 0:
			count = count + 1
		else:
			lst = []
			if j <= 5:
				for k in range(j):
					lst.append(p[k])
			else:
				e = j - 5
				for k in range(e, j):
					lst.append(p[k])
			if p[j] < min(lst):
				count = count + 1
	print(count)


for h in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = n
	for i in range(n):
		j = i - 1
		while j >= i - 5 and j >= 0:
			if l[i] >= l[j]:
				c -= 1
				break
			j -= 1
	print(c)


T = int(input())
for i in range(T):
	N = int(input())
	P = input()
	P = P.split()
	p = []
	for j in P:
		p.append(int(j))
	count = 1
	for i in range(1, N):
		minval = p[i]
		if i < 6 and minval < min(p[:i]):
			count += 1
		elif i >= 6 and minval < min(p[i - 5:i]):
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	count = 1
	for i in range(1, n):
		if i < 5:
			if p[i] < min(p[:i]):
				count += 1
		elif p[i] < min(p[i - 5:i]):
			count += 1
	print(count)


i = int(input())
x = 0
list1 = []
while x < i:
	pp = int(input())
	ss = input().split()
	ss2 = []
	for ele in ss:
		ss2.append(int(ele))
	of = [10000, 10000, 10000, 10000, 10000]
	ss2 = ss2[::-1]
	ss2 = ss2 + of
	ss2 = ss2[::-1]
	q = 5
	tot = 0
	while q < len(ss2):
		if ss2[q] < min(ss2[q - 5:q]):
			tot = tot + 1
		q = q + 1
	list1.append(tot)
	x = x + 1
for ele in list1:
	print(ele)


def check(lst, k):
	t = k - 1
	s = k
	l = 0
	if k >= 5:
		while t >= 0 and l <= 4:
			if lst[t] <= lst[k]:
				s = t
				break
			else:
				l = l + 1
				t = t - 1
	else:
		while t >= 0:
			if lst[t] <= lst[k]:
				s = lst[t]
				break
			else:
				t = t - 1
	if s == k:
		return 1
	else:
		return 0
b = int(input())
for i in range(b):
	N = int(input())
	a = list(map(int, input().split()))
	h = 0
	for i in range(len(a)):
		if check(a, i) == 1:
			h = h + 1
	print(h)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.reverse()
	c = 1
	for i in range(n):
		past = l[i + 1:i + 6]
		if len(past) == 0:
			break
		elif l[i] < min(past):
			c += 1
	print(c)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = [a[0]]
	c = 1
	for i in a[1:]:
		if i < min(x[-1:-6:-1]):
			c += 1
		x.append(i)
	print(c)


for _ in range(int(input())):
	n = int(input())
	l = list(input().split())
	fx = lambda k: (int(i) for i in k)
	do_the_honor = lambda l, func: [i for i in func(l)]
	final = do_the_honor(l, fx)
	k = 1
	for i in range(1, n):
		if i <= 5:
			if final[i] < min(final[:i]):
				k += 1
			else:
				pass
		elif final[i] < min(final[i - 5:i]):
			k += 1
		else:
			pass
	print(k)


for i in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	flag = [0] * n
	flag[0] = 1
	for j in range(n - 1):
		if flag[j] == 1 and lis[j + 1] < lis[j]:
			flag[j + 1] = 1
		if j < 5:
			k = j
		else:
			k = 4
		if flag[j] == 0 and min(lis[j - k:j + 1]) > lis[j + 1]:
			flag[j + 1] = 1
	print(sum(flag))


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	v = 1
	for i in range(2, n + 1):
		(temp, l) = (a[max(0, i - 6):i - 1], a[i - 1])
		if min(temp) > l:
			v += 1
	print(v)


t = int(input())
while t > 0:
	x = int(input())
	l = list(map(int, input().split()))
	count = 1
	list5 = [l[0]]
	for i in range(1, len(l)):
		if all((l[i] < y for y in list5)):
			count += 1
		if len(list5) < 5:
			list5.append(l[i])
		elif len(list5) == 5:
			list5.pop(0)
			list5.append(l[i])
	print(count)
	t -= 1


n = int(input())
list2 = [751, 751, 751, 751, 751]
for i in range(n):
	x = int(input())
	list1 = list(map(int, input().split()))
	list1 = list2 + list1
	p = 0
	for i in range(5, len(list1)):
		a = list1[i - 5]
		b = list1[i - 4]
		c = list1[i - 3]
		d = list1[i - 2]
		e = list1[i - 1]
		f = list1[i]
		r = min(a, b, c, d, e)
		if f < r:
			p += 1
	print(p)


for _ in range(int(input())):
	n = int(input())
	l = [int(j) for j in input().split()]
	count = 1
	for i in range(1, n):
		if i - 5 < 0:
			mini = min(l[0:i])
			if mini > l[i]:
				count += 1
		else:
			mini = min(l[i - 5:i])
			if mini > l[i]:
				count += 1
	print(count)


t = int(input())
for i in range(t):
	d = int(input())
	l = list(map(int, input().split()))
	l1 = []
	c = 0
	for j in range(d):
		if len(l1) == 0:
			c += 1
			l1.append(l[j])
		elif len(l1) == 5:
			if l[j] < min(l1):
				c += 1
			l1.pop(0)
			l1.append(l[j])
		else:
			if l[j] < min(l1):
				c += 1
			l1.append(l[j])
	print(c)


T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	count = 0
	for j in range(n):
		if j < 6 and j > 0:
			if l[j] < min(l[0:j]):
				count += 1
		if j > 5:
			if l[j] < min(l[j - 5:j]):
				count += 1
	print(count + 1)


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


bleh = int(input())
for i in range(bleh):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	c = 0
	for j in range(n):
		k = 0
		if j < 5:
			for p in range(j):
				if l[j] >= l[p]:
					k = 1
					break
		else:
			for p in range(j - 5, j):
				if l[j] >= l[p]:
					k = 1
					break
		if k == 0:
			c = c + 1
	print(c)


t = int(input())
for tc in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	a = [p[0]]
	v = 1
	for j in p[1:]:
		if j < min(a[-1:-6:-1]):
			v += 1
		a.append(j)
	print(v)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 1
	for i in range(1, n):
		if i < 5:
			if min(l[:i]) > l[i]:
				ans += 1
		elif min(l[i - 5:i]) > l[i]:
			ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	days = 1
	for i in range(1, n):
		flag = True
		for j in range(i - 1, i - 6, -1):
			if j >= 0:
				if l[i] >= l[j]:
					flag = False
					break
		if flag:
			days += 1
	print(days)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	k = p[0]
	c = 1
	for i in range(1, 6):
		if p[i] < k:
			k = p[i]
			c = c + 1
	for i in range(6, n):
		if k == p[i - 6]:
			value = None
			k = p[i - 5]
			for j in range(i - 4, i + 1):
				if p[j] < k:
					k = p[j]
					value = j
			if i == value:
				c = c + 1
		elif p[i] < k:
			k = p[i]
			c = c + 1
	print(c)


testcase = int(input())
for i in range(testcase):
	n = int(input())
	lst = list(map(int, input().split()))
	res = 1
	for j in range(1, n):
		rng = max(j - 5, 0)
		if lst[j] < min(lst[rng:j]):
			res += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ok = 0
		for j in range(i - 1, max(i - 5, 0) - 1, -1):
			if arr[j] <= arr[i]:
				ok = 1
				break
		if ok == 0:
			ans += 1
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	arr = [int(ele) for ele in input().split()]
	count = 1
	for i in range(1, N):
		if i < 5:
			if min(arr[:i]) > arr[i]:
				count += 1
		elif min(arr[i - 5:i]) > arr[i]:
			count += 1
	print(count)


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


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	c = 1
	min1 = s[0]
	for i in range(n):
		if i < 5:
			if min1 > s[i]:
				min1 = s[i]
				c += 1
		elif s[i] < s[i - 1] and s[i] < s[i - 2] and (s[i] < s[i - 3]) and (s[i] < s[i - 4]) and (s[i] < s[i - 5]):
			c += 1
	print(c)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = deque()
	ma = 100000000
	ans = 0
	for i in range(5):
		while d and a[d[0]] > a[i]:
			d.popleft()
		while d and a[d[-1]] > a[i]:
			d.pop()
		d.append(i)
		if a[i] < ma:
			ma = a[i]
			ans += 1
	for i in range(5, len(a)):
		if a[i] < a[d[0]]:
			ans += 1
		while d and a[d[0]] > a[i]:
			d.popleft()
		while d and a[d[-1]] > a[i]:
			d.pop()
		d.append(i)
		if i - d[0] == 5:
			d.popleft()
	print(ans)


a = int(input())
for i in range(a):
	n = int(input())
	arr = list(map(int, input().split()))
	sum = 1
	for i in range(1, n):
		if i < 5:
			if arr[i] < min(arr[:i]):
				sum += 1
		elif arr[i] < min(arr[i - 5:i]):
			sum += 1
	print(sum)


for _ in range(int(input())):
	n = int(input())
	s = list(map(int, input().split()))
	days = 1
	s = s[::-1]
	for i in range(n):
		lst = s[i + 1:i + 6]
		if len(lst) == 0:
			break
		elif s[i] < min(lst):
			days += 1
	print(days)


for t in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	c = 0
	ans = 1
	for i in range(5, n):
		for j in range(i - 1, i - 6, -1):
			if p[i] < p[j]:
				c = c + 1
		if c == 5:
			ans = ans + 1
		c = 0
	for i in range(1, 5):
		for j in range(i):
			if p[i] < p[j]:
				c = c + 1
		if c == i:
			ans = ans + 1
		c = 0
	print(ans)


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


def lastfive(l, i):
	ll = []
	for j in range(i - 5, i):
		ll.append(l[j])
	return ll
t = int(input())
for m in range(t):
	n = int(input())
	l = list(input().split(' '))
	c = 0
	for i in range(len(l)):
		if i == 0:
			c = 1
		elif i == 1:
			if l[i] < l[i - 1]:
				c = c + 1
		elif i == 2:
			if l[i] < l[i - 1] and l[i] < l[i - 2]:
				c = c + 1
		elif i == 3:
			if l[i] < l[i - 1] and l[i] < l[i - 2] and (l[i] < l[i - 3]):
				c = c + 1
		elif i == 4:
			if l[i] < l[i - 1] and l[i] < l[i - 2] and (l[i] < l[i - 3]) and (l[i] < l[i - 4]):
				c = c + 1
		else:
			f = lastfive(l, i)
			if l[i] < min(f):
				c = c + 1
	print(c)


for _ in range(int(input())):
	N = int(input())
	P = list(map(int, input().split()))
	l = [1000, 1000, 1000, 1000]
	P2 = l + P
	c = 1
	for i in range(0, N - 1):
		if min(P2[i:i + 5]) > P2[i + 5]:
			c += 1
	print(c)