For an array $[b_1, b_2, \ldots, b_m]$ define its number of inversions as the number of pairs $(i, j)$ of integers such that $1 \le i < j \le m$ and $b_i>b_j$. Let's call array $b$ odd if its number of inversions is odd.

For example, array $[4, 2, 7]$ is odd, as its number of inversions is $1$, while array $[2, 1, 4, 3]$ isn't, as its number of inversions is $2$.

You are given a permutation $[p_1, p_2, \ldots, p_n]$ of integers from $1$ to $n$ (each of them appears exactly once in the permutation). You want to split it into several consecutive subarrays (maybe just one), so that the number of the odd subarrays among them is as large as possible.

What largest number of these subarrays may be odd?


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 10^5$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$)  — the size of the permutation.

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$, all $p_i$ are distinct)  — the elements of the permutation.

The sum of $n$ over all test cases doesn't exceed $2\cdot 10^5$.


-----Output-----

For each test case output a single integer  — the largest possible number of odd subarrays that you can get after splitting the permutation into several consecutive subarrays.


-----Examples-----

Input
5
3
1 2 3
4
4 3 2 1
2
1 2
2
2 1
6
4 5 6 1 2 3
Output
0
2
0
1
1


-----Note-----

In the first and third test cases, no matter how we split our permutation, there won't be any odd subarrays.

In the second test case, we can split our permutation into subarrays $[4, 3], [2, 1]$, both of which are odd since their numbers of inversions are $1$.

In the fourth test case, we can split our permutation into a single subarray $[2, 1]$, which is odd.

In the fifth test case, we can split our permutation into subarrays $[4, 5], [6, 1, 2, 3]$. The first subarray has $0$ inversions, and the second has $3$, so it is odd.

Source: codeforces | Difficulty: EASY
Tags: Dynamic programming

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	prev = 0
	i = ans = 0
	while i < n:
		if not prev:
			prev = arr[i]
		elif prev > arr[i]:
			ans += 1
			prev = 0
		else:
			prev = arr[i]
		i += 1
	return ans
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

def solve():
	N = int(input())
	A = [int(x) for x in input().split()]
	z = 0
	i = 1
	while i < N:
		if A[i] <= A[i - 1]:
			z += 1
			i += 1
		i += 1
	return z
for _ in range(int(input())):
	print(solve())


import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
MOD = int(1000000000.0 + 7)
INF = int(1e+20)
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
t = int(input())
for _ in range(t):
	n = int(input())
	arr = li()
	res = 0
	pre = -1
	for i in arr:
		if pre == -1:
			pre = i
		elif i < pre:
			res += 1
			pre = -1
		else:
			pre = i
	print(res)


for s in [*open(0)][2::2]:
	a = (*map(int, s.split()),)
	print(sum((len(x) + 1 >> 1 for x in ''.join((' *'[x > y] for (x, y) in zip(a, a[1:]))).split())))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	w = list(map(int, input().split()))
	(i, c) = (0, 0)
	while i < n - 1:
		if w[i] > w[i + 1]:
			c += 1
			i += 1
		i += 1
	print(c)


for v in [*open(0)][2::2]:
	h = (*map(int, v.split()),)
	print(sum((len(x) + 1 >> 1 for x in ''.join((' *'[x > y] for (x, y) in zip(h, h[1:]))).split())))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def countZeros(num):
	length = num.bit_length()
	result = 0
	for i in range(length):
		if num & 1 << i:
			break
		result += 1
	return result

def main():
	for _ in range(inp()):
		n = inp()
		nums = inlt()
		maxVal = 0
		result = 0
		for num in nums:
			if num < maxVal:
				result += 1
				maxVal = 0
			else:
				maxVal = max(maxVal, num)
		print(result)
main()


for o in [*open(0)][2::2]:
	n = (*map(int, o.split()),)
	print(sum((len(y) + 1 >> 1 for y in ''.join((' *'[y > z] for (y, z) in zip(n, n[1:]))).split())))


inputt = open(0).read().split('\n')
for tc in range(int(inputt[0])):
	n = int(inputt[tc * 2 + 1])
	arr = list(map(int, inputt[tc * 2 + 2].split()))
	res = 0
	i = n - 2
	while i > -1:
		if arr[i] - arr[i + 1] > 0:
			i -= 1
			res += 1
		i -= 1
	print(res)


import atexit, io, os, sys
input = lambda : sys.stdin.readline().rstrip()
inputt = open(0).read().split('\n')
for tc in range(int(inputt[0])):
	n = int(inputt[tc * 2 + 1])
	arr = list(map(int, inputt[tc * 2 + 2].split()))
	res = 0
	i = n - 2
	while i > -1:
		if arr[i] - arr[i + 1] > 0:
			i -= 1
			res += 1
		i -= 1
	print(res)


for str in [*open(0)][2::2]:
	a = str.split()
	print(sum((len(x) + 1 >> 1 for x in ''.join((' *'[int(x) > int(y)] for (x, y) in zip(a, a[1:]))).split())))


import sys
input = sys.stdin.readline

def nextInt():
	return int(input())

def arrayIn():
	return list(map(int, input().split()))

def nextLine():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = nextInt()
while t > 0:
	n = nextInt()
	arr = arrayIn()
	ans = 0
	i = 0
	while i < n:
		if i + 1 < n and arr[i] > arr[i + 1]:
			ans += 1
			i += 1
		i += 1
	print(ans)
	t -= 1


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	co = 0
	i = 0
	while i < n - 1:
		if l[i] > l[i + 1]:
			co += 1
			i += 1
		i += 1
	print(co)


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


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


import atexit, io, os, sys
ss = io.BytesIO()
_write = ss.write
ss.write = lambda s: _write(s.encode())
atexit.register(lambda : os.write(1, ss.getvalue()))
input = lambda : sys.stdin.readline().rstrip()
inputt = open(0).read().split('\n')
for tc in range(int(inputt[0])):
	n = int(inputt[tc * 2 + 1])
	arr = list(map(int, inputt[tc * 2 + 2].split()))
	res = 0
	i = n - 2
	while i > -1:
		if arr[i] - arr[i + 1] > 0:
			i -= 1
			res += 1
		i -= 1
	print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	c = 0
	i = 0
	while i < N - 1:
		if A[i] > A[i + 1]:
			c += 1
			i += 1
		i += 1
	print(c)


import sys

def rall():
	return sys.stdin.readlines()

def rl():
	return sys.stdin.readline().strip()

def rl_types(types):
	str_list = [x for x in sys.stdin.readline().strip().split(' ')]
	return [types[i](str_list[i]) for i in range(len(str_list))]

def pr(something=''):
	sys.stdout.write(str(something) + '\n')

def pra(array):
	sys.stdout.write(' '.join([str(x) for x in array]) + '\n')

def solve(array):
	return array
NT = int(rl())
for ti in range(NT):
	n = int(rl())
	array = list(map(int, rl().split(' ')))
	max_subs = 0
	last = -1
	for (i, x) in enumerate(array):
		if last < 0:
			start = i
			last = x
		elif x > last:
			start = i
			last = x
		elif x < last:
			if (i - start) % 2 == 0:
				pass
			else:
				max_subs += 1
			last = -1
	print(max_subs)


import sys
ifs = sys.stdin
ofs = sys.stdout

def numbers_from_line(d=' '):
	return [int(s) for s in ifs.readline().strip().split(d) if len(s.strip()) > 0]

def solve(A):
	inv = 0
	n = len(A)
	if n == 1:
		return 0
	i = 0
	while i < n - 1:
		if A[i] > A[i + 1]:
			inv += 1
			i += 1
		i += 1
	return inv
T = int(ifs.readline())
for __ in range(T):
	n = int(ifs.readline())
	A = numbers_from_line()
	a = solve(A)
	ofs.write(str(a))
	ofs.write('\n')


def solve():
	input()
	nums = list(map(int, input().split()))
	s = 0
	prev_good = True
	for (a, b) in zip(nums, nums[1:]):
		if prev_good is False:
			prev_good = True
		elif a > b:
			s += 1
			prev_good = False
	print(s)
n = int(input())
for i in range(n):
	solve()


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split(' ')))
	ans = 0
	pas = False
	for i in range(1, n):
		if pas:
			pas = False
			continue
		if p[i - 1] > p[i]:
			ans += 1
			pas = True
	print(ans)


n = int(input())
l2 = []
for i in range(n):
	t = int(input())
	l = [int(x) for x in input().split()]
	l2.append(l)
for i in l2:
	c = i[0]
	s = 0
	for j in range(len(i)):
		if i[j] < c:
			try:
				c = i[j + 1]
				s += 1
			except:
				s += 1
		else:
			c = i[j]
	print(s)


def inversions_split(ar):
	n = len(ar)
	num_splits = 0
	ix = 0
	while ix < n - 1:
		if ar[ix] > ar[ix + 1]:
			ix += 1
			num_splits += 1
		ix += 1
	return num_splits
t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split(' ')))
	print(inversions_split(ar))


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


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	jump = 1
	number_of_inversions = 0
	i = 0
	while i < n - 1:
		if a[i] > a[i + 1]:
			number_of_inversions += 1
			i = i + 2
		else:
			i += 1
	print(number_of_inversions)


t = int(input())
res = [0] * t
for i in range(t):
	n = int(input())
	list1 = list(map(int, input().split()))
	j = 1
	while j < n:
		if list1[j] < list1[j - 1]:
			res[i] += 1
			j += 2
		else:
			j += 1
for i in res:
	print(i)


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


def main():
	tc = int(input())
	for _ in range(tc):
		n = int(input())
		arr = [int(a) for a in input().split()]
		i = 0
		ans = 0
		while i < n - 1:
			if arr[i] > arr[i + 1]:
				i += 1
				ans += 1
			i += 1
		print(ans)
main()


T = int(input())
while T:
	N = int(input())
	li = list(map(int, input().split()))
	curr_min = None
	ans = 0
	for ele in li:
		if curr_min:
			if curr_min > ele:
				ans += 1
				curr_min = None
			else:
				curr_min = ele
		else:
			curr_min = ele
	print(ans)
	T -= 1


def solve():
	if n == 1:
		return 0
	count = 0
	curr_max = arr[0]
	for i in range(1, n):
		if curr_max == -1:
			curr_max = arr[i]
			continue
		if curr_max > arr[i]:
			count += 1
			curr_max = -1
		else:
			curr_max = arr[i]
	return count
T = int(input())
for t in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = solve()
	print(ans)


def per():
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	i = 0
	j = 1
	while j < n:
		if l[i] > l[j]:
			c += 1
			i = i + 2
			j = j + 2
		else:
			i = i + 1
			j = j + 1
	print(c)
t = int(input())
while t:
	per()
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	count = 0
	i = 0
	while i <= n - 2:
		if a[i] > a[i + 1]:
			count += 1
			i += 2
		else:
			i += 1
	print(count)


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


def func():
	n = int(input())
	l = input().split(' ')
	l = [int(i) for i in l]
	i = 0
	c1 = 0
	while i < n - 1:
		if l[i] > l[i + 1]:
			c1 += 1
			i += 2
		else:
			i += 1
	return c1
t = int(input())
for i in range(t):
	ans = func()
	print(ans)


aws = []
T = int(input())
for i in range(T):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	c = 0
	j = 0
	while len(l) - 1 > j:
		if l[j] > l[j + 1]:
			j += 2
			c += 1
		else:
			j += 1
	aws.append(c)
for i in aws:
	print(i)


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


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


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	c = 0
	i = 1
	while i < n:
		if arr[i] < arr[i - 1]:
			c += 1
			i += 2
		else:
			i += 1
	print(c)
	t -= 1


def main():
	cas = int(input())
	for _ in range(cas):
		n = int(input())
		arr = list(map(int, input().split()))
		cnt = 0
		i = 0
		while i < n - 1:
			if arr[i] > arr[i + 1]:
				cnt = cnt + 1
				i = i + 2
			else:
				i = i + 1
		print(cnt)
main()


def check(arr):
	count = 0
	n1 = len(arr)
	i = 1
	while i < n1:
		j = i
		while j < n1 and arr[j] >= arr[j - 1]:
			j += 1
		if j >= n1:
			break
		count += 1
		i = j + 2
	return count
n = int(input())
for i in range(n):
	s = int(input())
	ar = list(map(int, input().split()))
	print(check(ar))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m = 0
	ans = 0
	for i in l:
		if i > m:
			m = i
		else:
			ans += 1
			m = 0
	print(ans)


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


def solve():
	n = int(input())
	p = [int(i) for i in input().split()]
	res = 0
	i = 0
	while i + 1 < n:
		if p[i] > p[i + 1]:
			res += 1
			i += 1
		i += 1
	print(res)
t = int(input())
while t > 0:
	t -= 1
	solve()


t = int(input())

def solve():
	x = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	i = 0
	while i < len(arr) - 1:
		if arr[i] > arr[i + 1]:
			ans += 1
			i += 2
		else:
			i += 1
	print(ans)
for i in range(t):
	solve()


t = int(input())

def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	i = 0
	while i < n - 1:
		if arr[i + 1] < arr[i]:
			i += 2
			ans += 1
		else:
			i += 1
	print(ans)
while t:
	solve()
	t -= 1


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


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


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	for i in a:
		if (s - i) / (n - 1) == i:
			return 'YES'
	return 'NO'

def sol():
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	i = 0
	while i < n - 1:
		if a[i] > a[i + 1]:
			ans += 1
			i += 1
		i += 1
	return ans
for _ in range(int(input())):
	print(sol())


def main():
	cases = int(input())
	for _ in range(cases):
		n = int(input())
		arr = [int(x) for x in input().split()]
		ans = 0
		i = 0
		while i < n - 1:
			if arr[i] > arr[i + 1]:
				ans += 1
				i += 1
			i += 1
		print(ans)
main()


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


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = 0
	mx = arr[0]
	i = 1
	while i < n:
		if mx > arr[i]:
			cnt += 1
			if i != n - 1:
				mx = arr[i + 1]
			i += 2
		else:
			mx = max(mx, arr[i])
			i += 1
	print(cnt)
	return
t = int(input())
while t:
	t -= 1
	solve()


def li():
	return list(map(int, input().split()))

def mi(n):
	return [list(map(int, input().split())) for _ in range(n)]
t = int(input())
for _ in range(t):
	n = int(input())
	l = li()
	i = 0
	ans = 0
	while i < n - 1:
		j = i + 1
		if l[i] > l[j]:
			ans += 1
			i = j + 1
		else:
			i = j
	print(ans)