问题1559--最强阵容加强版

1559: 最强阵容加强版

时间限制: 1 Sec  内存限制: 128 MB
提交: 87  解决: 44
[提交] [状态] [讨论版] [命题人:]

题目描述

拿着新换来的英雄卡,小李满心欢喜的准备和同学们PK一下。
他们的游戏规则非常简单,双方把自己的牌绕成一圈,然后指定一个起点,从该张牌开始顺时针方向往后取,谁取出的字符串字典序更小(从左到右开始比较,碰到第一个不一样的字符进行比较,比较规则为a<b<…<z)谁将获得胜利。具体规则可参考样例。虽然现在小李的牌已经很好了,但是你能不能帮他快速算出起始位置,使得他能够派出最强阵容。

输入

第一行n,表示共有n张牌。
第二行共n个用一个空格隔开的小写字母,表示给定的一圈牌起始序列。

输出

仅一个整数,能获得最小字典序字符串的起点位置。如果有多个位置开始的字符串一样,则输出最小的那个位置,且第一个位置从1开始。

样例输入 Copy

4
b c a b

样例输出 Copy

3

提示

【样例说明】
四个位置取出的字符串分别为bcab,cabb,abbc,bbca,显然最小位置是3。
【数据规模】
30%的数据,1<=n<=10
60%的数据,1<=n<=1000
100%的数据,1<=n<=300000

来源/分类