Rotated but Sorted

Difficulty: 1300 3500 ms 128 MB

implementation

Is the array a rotation of some non-decreasing array?

Input: the first line has N; the second line has N integers.

Output: YES or NO.

Constraints:

• 1 ≤ N ≤ 10⁵
• |a_i| ≤ 10⁹

Sample Tests

5
3 4 5 1 2

YES

4
2 1 3 1

NO

Read the Editorial