## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Chef and Array CodeChef Solution | Solution CodeChef

## Problem

Chef has an array $A$ consisting of $N$ elements. Chef also has $2$ empty arrays $B$ and $C$.

Chef performs the following algorithm on the arrays:

• Step $1$: While array $A$ is not empty, Chef removes the last element of $A$ and places it in the middle of array $B$. If $B$ currently has odd length, Chef can place the element from $A$ to the left or to the right of the middle element of $B$. As a result, array $A$ becomes empty and $B$ now consists of $N$ elements.
• Step $2$: While array $B$ is not empty, Chef removes the last element of $B$ and places it in the middle of array $C$. If $C$ currently has odd length, Chef can place the element from $B$ to the left or to the right of the middle element of $C$. As a result, array $B$ becomes empty and $C$ now consists of $N$ elements.

Determine whether he can make array $C$ sorted in non-decreasing order. Formally, determine whether he can generate the array $C$ such that $C_i \le C_{(i+1)}$ for each $(1 \le i \lt N)$.

### Input Format

• The first line contains an integer $T$, the number of test cases.
• Then the test cases follow. The first line of each test case contains a single integer $N$ - the length of the array $A$.
• The second line contains $N$ space-separated integers, the elements of the array $A$.

Solution Click Below:-  👉
👇👇👇👇👇

### Output Format

For each test case, output YES if you can make array $C$ sorted in non-decreasing order, otherwise, print NO.

You may print each character of the string in uppercase or lowercase (for example, the strings YESyEsyes, and yeS will all be treated as identical).

### Explanation:

Test case $1$: We can do the following for $A = [3,1,5,3]$:

• Step $1$$A = [3,1,5,3], B = [] \rightarrow A = [3,1,5], B = [3] \rightarrow A = [3,1], B = [3, 5]\rightarrow A = [3], B = [3, 1, 5] \rightarrow A = [], B = [3, 3, 1, 5]$.
• Step $2$$B = [3,3,1,5], C = [] \rightarrow B = [3,3,1], C = [5] \rightarrow B = [3,3], C = [1, 5]\rightarrow B = [3], C = [1,3, 5] \rightarrow B = [], C = [1, 3, 3, 5]$.

As a result, array $C=[1,3,3,5]$ and it is sorted.

Test case $2$: We cannot generate array $C$ in sorted order.