Pseudo Sorted Array Solution | CodeChef Problem Solution 2022 | April Long Two

Pseudo Sorted Array Solution | CodeChef Problem Solution 2022 | April Long Two

An array A$A$ of length N$N$ is said to be pseudo-sorted if it can be made non-decreasing after performing the following operation at most once.

• Choose an i$i$ such that 1≤i≤N−1$1\le i\le N-1$ and swap Ai$A_i$ and Ai+1$A_{i+1}$

Given an array A$A$, determine if it is pseudo-sorted or not.

Input Format

• The first line contains a single integer T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ - the size of the array A$A$.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the array A$A$.

Output Format

For each testcase, output YES if the array A$A$ is pseudo-sorted, NO otherwise.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 2≤N≤105$2\le N\le {10}^5$
• 1≤Ai≤109$1\le A_i\le {10}^9$
• Sum of N$N$ over all test cases do not exceed 2⋅105$2\cdot {10}^5$

Sample Input 1 

3
5
3 5 7 8 9
4
1 3 2 3
3
3 2 1

Sample Output 1 

YES
YES
NO

Explanation

Test case 1: The array is already sorted in non-decreasing order.

Test case 2: We can choose i=2$i=2$ and swap A2$A_2$ and A3$A_3$. The resulting array will be [1,2,3,3]$[1,2,3,3]$, which is sorted in non-decreasing order.

Test case 3: It can be proven that the array cannot be sorted in non-decreasing order in at most one operation.

Akash and Equal Mean Solution | CodeChef Problem Solution 

Flip to Invert Solution CodeChef 

Antipodal Points Solution

Best Coupon Solution | CodeChef Problem Solution 2022

Join Now for Solution:- 

Sasta Shark Tank Solution | CodeChef Problem Solution