# [Solution] Pseudo Sorted Array solution codechef

Pseudo Sorted Array solution codechef – An array AA of length NN is said to be pseudo-sorted if it can be made non-decreasing after performing the following operation at most once.

## [Solution] Pseudo Sorted Array solution codechef

• Choose an ii such that 1iN11≤i≤N−1 and swap AiAi and Ai+1Ai+1

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

### Input Format

• The first line contains a single integer TT – the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer NN – the size of the array AA.
• The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN denoting the array AA.

### Output Format

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

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

## [Solution] Pseudo Sorted Array solution codechef

• 1T10001≤T≤1000
• 2N1052≤N≤105
• 1Ai1091≤Ai≤109
• Sum of NN over all test cases do not exceed 21052⋅105

### 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


## Pseudo Sorted Array solution Explanation

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

Test case 2: We can choose i=2i=2 and swap A2A2 and A3A3. 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.