Array Rotation Sorting

You are given an array of integers. Your task is to determine if the array can be rotated to become sorted in non-decreasing order. A rotation means splitting the array into two parts and swapping their order. Formally, you need to check if there exists an index such that when the array is rotated at that index, the resulting array satisfies \(a_i \leq a_{i+1}\) for every valid index (consider the array in a circular fashion).

For example, the array [3, 4, 5, 6, 1, 2] can be rotated to obtain [1, 2, 3, 4, 5, 6] which is sorted, whereas the array [4, 3, 2, 1] cannot be rotated in any way to form a sorted array.

inputFormat

The first line contains an integer \(n\), the number of elements in the array. The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Print True if the array can be rotated to become sorted in non-decreasing order; otherwise, print False.

6
3 4 5 6 1 2

True