[Solution] Chef and Array CodeChef Solution

[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:-  👉CLICK HERE👈

👇👇👇👇👇

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 YES, yEs, yes, 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.