A-B-C Sort (Codeforces 1674D)
Tags: Others, sortings

You are given three arrays $$$a$$$, $$$b$$$ and $$$c$$$. Initially, array $$$a$$$ consists of $$$n$$$ elements, arrays $$$b$$$ and $$$c$$$ are empty.You are performing the following algorithm that consists of two steps:   Step $$$1$$$: while $$$a$$$ is not empty, you take the last element from $$$a$$$ and move it in the middle of array $$$b$$$. If $$$b$$$ currently has odd length, you can choose: place the element from $$$a$$$ to the left or to the right of the middle element of $$$b$$$. As a result, $$$a$$$ becomes empty and $$$b$$$ consists of $$$n$$$ elements.  Step $$$2$$$: while $$$b$$$ is not empty, you take the middle element from $$$b$$$ and move it to the end of array $$$c$$$. If $$$b$$$ currently has even length, you can choose which of two middle elements to take. As a result, $$$b$$$ becomes empty and $$$c$$$ now consists of $$$n$$$ elements.  Refer to the Note section for examples.Can you make array $$$c$$$ sorted in non-decreasing order?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Next $$$t$$$ cases follow.The first line of each test case contains the single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the array $$$a$$$ itself.It's guaranteed that the sum of $$$n$$$ doesn't exceed $$$2 \cdot 10^5$$$.

Output: For each test, print YES (case-insensitive), if you can make array $$$c$$$ sorted in non-decreasing order. Otherwise, print NO (case-insensitive).

Note: In the first test case, we can do the following for $$$a = [3, 1, 5, 3]$$$:Step $$$1$$$: $$$a$$$$$$[3, 1, 5, 3]$$$$$$\Rightarrow$$$$$$[3, 1, 5]$$$$$$\Rightarrow$$$$$$[3, 1]$$$$$$\Rightarrow$$$$$$[3]$$$$$$\Rightarrow$$$$$$[]$$$$$$b$$$$$$[]$$$$$$[\underline{3}]$$$$$$[3, \underline{5}]$$$$$$[3, \underline{1}, 5]$$$$$$[3, \underline{3}, 1, 5]$$$Step $$$2$$$: $$$b$$$$$$[3, 3, \underline{1}, 5]$$$$$$\Rightarrow$$$$$$[3, \underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{3}, 5]$$$$$$\Rightarrow$$$$$$[\underline{5}]$$$$$$\Rightarrow$$$$$$[]$$$$$$c$$$$$$[]$$$$$$[1]$$$$$$[1, 3]$$$$$$[1, 3, 3]$$$$$$[1, 3, 3, 5]$$$ As a result, array $$$c = [1, 3, 3, 5]$$$ and it's sorted.

Sample Inputs:
3
4
3 1 5 3
3
3 2 1
1
7331

Sample Outputs:
YES
NO
YES

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    a = list(map(int, readline().split()))
    for i in range(n - 1, 0, -2):
        if a[i - 1] > a[i]:
            (a[i - 1], a[i]) = (a[i], a[i - 1])
    ok = True
    for i in range(1, n):
        if a[i - 1] > a[i]:
            ok = False
            break
    print('YES' if ok else 'NO')

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def solve():
    inp = sys.stdin.readline
    n = int(inp())
    a = list(map(int, inp().split()))
    b = sorted(a)
    for i in range(n % 2, n, 2):
        if not (a[i] == b[i] and a[i + 1] == b[i + 1] or (a[i] == b[i + 1] and a[i + 1] == b[i])):
            print('NO')
            return
    print('YES')

def main():
    for i in range(int(sys.stdin.readline())):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n = int(input())
    nums = list(map(int, input().split()))
    nums_copy = nums.copy()
    nums_copy.sort()
    start = 0
    if n % 2:
        if nums_copy[0] != nums[0]:
            print('NO')
            continue
        start = 1
    imp = False
    for i in range(start, n - 1, 2):
        if not sorted(nums[i:i + 2]) == nums_copy[i:i + 2]:
            imp = True
            break
    if imp:
        print('NO')
    else:
        print('YES')