You’re given a rotated sorted array, arr, of length $n$, that is rotated clockwise between $1$ and $n$ times.

For example,

• Before rotation, arr $= [1,2,3,4,5,6,7,8]$

• After $3$ rotations, the array becomes $[6,7,8,1,2,3,4,5]$.

Mathematically, we can say that if the original array was $[a[0],a[1],a[2], ... ,a[n−1]]$, then each rotation changes the array as follows:

• First rotation: $[a[n−1],a[0],a[1],a[2],...,a[n−2]]$

• Second rotation: $[a[n−2],a[n−1],a[0],a[1],a$ ...