One Subarray Sorting

You are given an array of integers. Your task is to determine whether the array can be sorted into non-decreasing order by performing a single contiguous subarray sorting operation. In other words, find if there exist two indices \(l\) and \(r\) (with \(1 \leq l \leq r \leq n\)) such that by sorting the subarray from index \(l\) to \(r\) (1-indexed), the entire array becomes sorted.

If the array is already sorted, it is considered valid. Note that sorting means rearranging the elements in non-decreasing order.

Constraints:
1 ≤ n ≤ 10⁵
The array may contain duplicate elements.

Hint: Identify the first segment where the order breaks, and then determine if sorting only that segment will yield a fully sorted array.

inputFormat

The input begins with an integer T, representing the number of test cases. Each test case starts with an integer n (the size of the array) on a new line, followed by a line of n space-separated integers representing the array elements.

outputFormat

For each test case, output "YES" if the array can be sorted into non-decreasing order by sorting one contiguous subarray (or if it is already sorted); otherwise, output "NO". Each result should be printed on a separate line.## sample

4
5
1 2 5 4 3
4
4 3 2 1
6
1 3 5 2 4 6
5
1 2 3 4 5

YES
YES
NO
YES