MINMOVE - Minimum Rotations

Given a string S[1..n] . A rotation on S is that we move the first character to the right-most of the string. More specific, after a rotation, S becomes T = S[2..n] + S[1].

For example: S = abcaa, then after a rotation we have S = bcaaa.

Find the minimum number of rotations to make S become the smallest lexicographical order string.

Input

A single line contains a string S. S contains only small letters of English alphabet (ā€˜aā€™ .. ā€˜zā€™), and the length of S is not more than 100000.

Output

A single line contains an integer which represents the minimum number of rotations.

Example

Input:
mississippi

Output:
10

Test cases and time limit have been updated. Some accepted solution got TLE.


Added by:Race with time
Date:2008-12-29
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO PERL6
Resource:Based on a problem from ACM Central European Programming Contest

hide comments
2024-06-30 16:25:59
@coolcoder_iith How did you know it timed out at 12?

Finally my O(n*logn) solution got accepted. My previous attempt of O(n*logn*logn) solution gave a TLE

Last edit: 2024-06-30 16:41:18
2019-10-03 20:19:13
time out at #12
what to do
2019-09-15 17:47:12 yaswanth
Tried n*logn*logn with quite number of optimisations. TLE
n*logn went through though
2018-08-23 23:15:18
Was getting WA on #17 with prefix hash

Made my for loop that compared the current solution with a new candidate run twice instead of once

Got AC
2016-09-30 13:29:49
learned a lot :D
2016-09-11 19:19:06
Those who are using stl, make sure to use stable_sort if using nlogn*logn solution. Costed me few WA
2016-04-03 05:42:51 minhthai
"Some accepted solution got TLE."
Please, give some care to Java nlogn solution :((
2016-02-05 15:33:28
Same as http://www.spoj.com/problems/BEADS/ . O(nlogn) passed. :)
2016-01-22 05:30:20 Dhawal Harkawat
silly mistake costed two WAs at #10. finally AC.
2016-01-21 23:37:21 Sumit Vohra
solved using suffix automaton in O(n)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.