661. Was It Sorted Before Someone Rotated It

An array is given. Decide whether it could have been obtained by taking a NON-DECREASING array and rotating it some number of places, possibly zero.

Print Yes or No.

3 4 5 1 2 -> Yes rotating 1 2 3 4 5 by three 2 1 3 4 -> No 1 2 3 -> Yes rotated by zero

## Count the steps down, around the circle

Walk the array treating it as a CIRCLE, so the position after the last is the first again. Count how many times a value is followed by a strictly smaller one.

A sorted array rotated by r places has exactly ONE such step down when r is not a multiple of the length, and NONE when the array is already sorted and all values are equal or the rotation is zero.

So the answer is Yes exactly when the number of steps down is at most 1.

## Why at most one is the whole test

If there are no steps down at all, every value is at most the next one all the way round, which forces every value to be equal. That is certainly a rotated sorted array.

If there is exactly one, cut the circle there: the piece after the cut runs up to the end and the piece before it continues, and joining them gives a non-decreasing array. So the input is that array rotated.

If there are two or more, any cut leaves at least one step down inside, and a non-decreasing array has none. So no rotation works.

## Why the circular comparison matters

Comparing only adjacent positions inside the array misses the wrap. 2 3 1 has one internal step down and IS a rotation. 3 1 2 also has one internal step down and is a rotation too. But 1 3 2 has one internal step down and is NOT: the wrap from 2 back to 1 is a second step down, and counting it is what rejects the input.

Forgetting the wrap accepts 1 3 2 and is the single mistake this problem is built around.

## Equal values

Equal neighbours are not a step down, so an array of identical values answers Yes with zero steps.

## Cost

Time O(n) in one pass. Space O(1).

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ each value ≤ 10^9`