algorithm - Counting the number of moves for sorting an array if only unit shift are allowed -

so, have array containing integers. need sort it. however, operation can perform unit shift. is, can move last element of sequence beginning.

          `a1, a2, ..., an → an, a1, a2, ..., an - 1.` 

what minimum number of operations need sort sequence?

the number of integers in array can upto 10^5. , each integer individual value can 10^5 too. also, if array sorted, print 0 else if array cannot sorted unit shifts, print -1.

the solution thought of:

1. check if array sorted or not.
2. if array sorted, print 0 else
3. set count = 0
4. rotate array 1 unit , increment count.
5. check if array sorted: if yes, print count , break, else
6. repeat steps 4-5 till count < (total integers in array).

now, above solution has time complexity of o(n^2). because, checking each individual element if array sorted , checking takes o(n) time, , have n elements, makes o(n^2).

can suggest me other better approach? thanks!

ps: tried hard thinking of other approach. reached uptill counting inversions, doesn't help.

just iterate array, find first index i such arr[i] > arr[i+1] (if there no such index, done since array sorted), check if arr[i+1],...,arr[n] sorted, , if arr[n] <= arr[1]. if is, can done doing n-i rotations.

otherwise, there no solution.

time complexity o(n), space complexity o(1).

---

appendix: correctness of algorithm:

claim 1:

if array cannot splitted 2 arrays arr[1],arr[2],..,arr[i] , arr[i+1],...,arr[n] - both sorted, there no solution.

proof:
let's assume i first index arr[i] > arr[i+1], , let j other index such arr[j] > arr[j+1], j!=i. there must such because arr[i+1],...,arr[n] unsorted.

by definition, while j+1 not "unit shifted", array unsorted.
immidiately after shifted, still not sorted since arr[i] > arr[i+1], , after shift, arr[j] again before arr[j+1], , violating sorted order.
thus, array cannot sorted.

claim 2:

assume array can splitted 2 sorted array arr[1],...,arr[i], , arr[i+1],...,arr[n].
also assume arr[i] > arr[i+1].
then, array can "unit shifted" sorted one, if , if arr[n] <= arr[1].

proof:

<---
the array not sorted, @ least 1 unit shift must done. unit shift places arr[n] before arr[1], , array never sorted unless arr[n]<=arr[1]

--->
assume arr[n]<=arr[1], shifting arr[i+1],...,arr[n], following array:

arr[i+1],arr[i+2],...,arr[n],arr[1],arr[2],...,arr[i] 

note arr[i+1]<= arr[i+2] <= .... <= arr[n] since assumed sorted.
similarly arr[1]<=arr[2]<=...<=arr[i]
also note arr[n] <= arr[i], assumption.

by joining 3 above inequalities get:

arr[i+1] <= arr[i+2] <= ... <= arr[n] m= arr[1] <= arr[2] <= ... <= arr[i] 

the above definition sorted array, concludes proof claim.

claim 3:

the algorithm correct

by applying claim1,claim2 , handling case array sorted, that:

the array can sorted using "unit shifts" if , if: sorted, or conditions of claim2 applies, , concludes proof.

qed