At Nightfall Amusement Park, the Solstice Wheel has n gondolas bolted to its rim at equal intervals. When the ride was assembled, the gondola numbers were attached going clockwise starting from a fixed reference bolt so that reading them clockwise from that bolt gave a non-decreasing sequence (repeated numbers are allowed). After assembly, maintenance crews are allowed to rotate the entire wheel to a new resting position — sliding every gondola forward by the same number of clicks — but they never unbolt or reorder gondolas relative to each other.
A safety inspector walks up to the reference bolt today and records the n gondola numbers clockwise starting from that bolt. Given this recording, decide whether it is possible that the wheel still has its original assembled numbering (possibly after zero or more whole rotations), or whether the recording proves the gondolas were tampered with (reordered) at some point.
Print YES if the recorded sequence is consistent with some rotation of a non-decreasing clockwise assembly order, or NO otherwise.
Example 1
Input
4 3 4 5 1
Expected
YES
Explanation
Reading clockwise from the reference bolt gives 3, 4, 5, 1. Rotating this reading back by one position (moving the 1 to the front) yields 1, 3, 4, 5, which is non-decreasing. There is exactly one clockwise drop, from 5 down to 1 at the wrap-around, which is exactly what a valid rotation produces, so the answer is YES.
Example 2
Input
4 2 1 3 4
Expected
NO
Explanation
Going clockwise there is a drop from 2 to 1 in the middle of the sequence, and another drop when wrapping from 4 back around to 2. A sequence produced by rotating a non-decreasing assembly can have at most one such clockwise drop (at the rotation point); having two drops proves no rotation of a non-decreasing arrangement could look like this, so the answer is NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →