Given a rotated sorted array, recover it to sorted array in-place. A rotated array is an array in which its elements are shifted. For example, [3, 4, 1, 2] is a rotated array of array [1, 2, 3, 4] by 2 places.

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

The algorithm should run in-place with O(1) space and O(n) time.