Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

For a sequence of positive integers $A_{1}, A_{2}, \ldots, A_{K}$, let's define the number of inversions in it as the number of pairs of integers $(i, j)$ such that $1 ≤ i < j ≤ K$ and $A_{i} > A_{j}$.

You are given a permutation $P_{1}, P_{2}, \ldots, P_{N}$ of the integers $1$ through $N$. Determine if it is possible to partition this permutation into two subsequences (possibly empty or non-contiguous) such that:
Each element of $P$ appears in exactly one of these subsequences.
The numbers of inversions in one subsequence is equal to the number of inversions in the other subsequence.

------  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}, \ldots, P_{N}$.

------  Output ------
For each test case, print a single line containing the string "YES" if it is possible to partition the permutation in a given way or "NO" if it is impossible.

------  Constraints ------
$1 ≤ N ≤ 100$
$1 ≤ P_{i} ≤ N$ for each valid $i$
$P_{1}, P_{2}, \ldots, P_{N}$ are pairwise distinct
the sum of $N$ over all test cases does not exceed $200$

------  Subtasks ------
Subtask #1 (20 points): $N ≤ 16$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
4

1

1

3

3 2 1

4

4 3 2 1

5 

1 4 3 2 5
----- Sample Output 1 ------ 
YES

NO

YES

NO
----- explanation 1 ------ 
Example case 1: We can split $(1)$ into $(1)$ and $()$. There are $0$ inversions in each of these sequences.

Example case 3: We can split $(4, 3, 2, 1)$ into $(4, 3)$ and $(2, 1)$. There is $1$ inversion in each of them. Note that this is not the only solution ? we could also split the permutation into sequences $(4, 1)$ and $(3, 2)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming

Constructive algorithms

Ad-hoc


Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	f = [0] * n
	for j in range(n):
		for k in range(j + 1, n):
			if l[j] > l[k]:
				f[j] += 1
				f[k] += 1
	w = sum(f) // 2
	p = [False] * (w + 1)
	p[0] = True
	for v in f:
		for z in range(w - v, -1, -1):
			p[z + v] |= p[z]
	print('YES' if p[w] else 'NO')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	inv = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				inv[i] += 1
				inv[j] += 1
	rj = sum(inv) // 2
	dp = [False] * (rj + 1)
	dp[0] = True
	for i in inv:
		for j in range(rj - i, -1, -1):
			dp[i + j] |= dp[j]
	if dp[rj]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	inv = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if l[i] > l[j]:
				inv[i] += 1
				inv[j] += 1
	want = sum(inv) // 2
	poss = [False] * (want + 1)
	poss[0] = True
	for v in inv:
		for i in range(want - v, -1, -1):
			poss[i + v] |= poss[i]
	if poss[want]:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	lst = list(map(int, input().split()))
	inversionarray = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if lst[i] > lst[j]:
				inversionarray[i] = inversionarray[i] + 1
				inversionarray[j] = inversionarray[j] + 1
	var = sum(inversionarray) // 2
	barr = [0] * (var + 1)
	barr[0] = 1
	for x in inversionarray:
		for i in range(var - x, -1, -1):
			barr[i + x] |= barr[i]
	if barr[var]:
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	inv = [0] * n
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				inv[i] += 1
				inv[j] += 1
	want = sum(inv) // 2
	dp = [False] * (want + 1)
	dp[0] = True
	for i in inv:
		for j in range(want - i, -1, -1):
			dp[i + j] |= dp[j]
	if dp[want]:
		print('YES')
	else:
		print('NO')


def knapSack(W, wt, val, n):
	K = [[0 for x in range(W + 1)] for x in range(n + 1)]
	for i in range(n + 1):
		for w in range(W + 1):
			if i == 0 or w == 0:
				K[i][w] = 0
			elif wt[i - 1] <= w:
				K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
			else:
				K[i][w] = K[i - 1][w]
	return K[n][W]
t = int(input())
for _ in range(t):
	N = int(input())
	A = [int(x) for x in input().split()]
	delta = 0
	C = []
	for i in range(len(A)):
		for j in range(i + 1, len(A)):
			if A[i] > A[j]:
				delta += 1
	for i in range(len(A)):
		c = 0
		for j in range(len(A)):
			if i > j and A[j] > A[i]:
				c += 1
			if i < j and A[i] > A[j]:
				c += 1
		C.append(c)
	W = delta
	val = C.copy()
	wt = C.copy()
	n = len(C)
	reachable_sum = knapSack(W, wt, val, n)
	if reachable_sum - delta == 0:
		print('YES')
	else:
		print('NO')


import numpy as np

def inversions(P):
	N = len(P)
	arr = np.zeros((N, N), dtype=int)
	for i in range(len(P)):
		for j in range(len(P)):
			if i < j and P[i] > P[j]:
				arr[i, j] = 1
				arr[j, i] = 1
	invs = arr.sum(0)
	res = sorted([x for x in invs if x > 0])
	return res

def isSubsetSum(arr, n, tot):
	subset = [[False for i in range(tot + 1)] for i in range(n + 1)]
	for i in range(n + 1):
		subset[i][0] = True
	for i in range(1, tot + 1):
		subset[0][i] = False
	for i in range(1, n + 1):
		for j in range(1, tot + 1):
			if j < arr[i - 1]:
				subset[i][j] = subset[i - 1][j]
			if j >= arr[i - 1]:
				subset[i][j] = subset[i - 1][j] or subset[i - 1][j - arr[i - 1]]
	return 'YES' if subset[n][tot] else 'NO'
for _ in range(int(input())):
	N = int(input())
	P = [int(x) for x in input().split()]
	arr = inversions(P)
	n = len(arr)
	tot = sum(arr) // 2
	print(isSubsetSum(arr, n, tot))


from sys import stdin, stdout, setrecursionlimit
import heapq
from math import gcd, ceil, sqrt
from collections import Counter, deque
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
setrecursionlimit(100000)
mod = 1000000007

def get(tot, cnt):
	dp = [[0 for i in range(tot + 1)] for j in range(len(cnt) + 1)]
	for i in range(1, len(cnt) + 1):
		for j in range(tot + 1):
			if j == 0:
				dp[i][j] = 1
			elif j < cnt[i - 1]:
				dp[i][j] = dp[i - 1][j]
			else:
				dp[i][j] = dp[i - 1][j] or dp[i - 1][j - cnt[i - 1]]
	return dp[-1][-1]
tc = ii1()
for _ in range(tc):
	n = ii1()
	arr = iia()
	cnt = [0] * n
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			if arr[i] > arr[j]:
				cnt[i] += 1
				cnt[j] += 1
	req = sum(cnt) // 2
	if get(req, cnt):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	p = [int(i) for i in input().split()]
	c = [0] * n
	total = 0
	for i in range(n):
		for j in range(i + 1, n):
			if p[i] > p[j]:
				c[i] += 1
				c[j] += 1
				total += 1
	dp = [False] * (total + 1)
	dp[0] = True
	for x in c:
		for i in range(total - x, -1, -1):
			dp[i + x] |= dp[i]
	if dp[total]:
		print('YES')
	else:
		print('NO')