Given a string 's', we can perform the following operation:-

1) Choose an index 'i' greater than the previous index and rotate the suffix(left or right rotate) formed from i, any number of times.

What is the minimum number of operations required to make smallest possible lexicographical string from s?

Size of input:- length of string<=10^5

Example:-

1) s:- acab

Choose suffix from index 1 and right rotate the string "cab" 2 times to the right to obtain "aabc" which is the smallest possible lexicographical string.

So the minimum number of operations required is 1.

2) s:- cdax

First, choose suffix from index 0 and rotate the string "cdax" two times to the right to get "axad".

Now choose suffix from index 1 and rotate the string "xad" 1 time to the left to obtain "adx". Final string is "aadx".

So minimum number of operations required is 2.

Note:- In a single operation you can perform any number of left or right rotations on a suffix.