题目描述

终于，卡卡西过关斩将，从芭比阿姨家摘得了自己所需要的所有的字母水晶珠，她捧着这些水晶珠，回到妈妈身边。妈妈高兴万分，摸着卡卡西的头说：“太棒了，宝贝，下面，你想不想学习一种特别的制作项链的方式呢？”卡卡西眨巴着水灵灵的大眼睛，好奇的问：“当然想啦，怎么特别呢？”，妈妈说：“这是一条很长而且独特的项链。这个项链需要由连接在一起的各种大小不同的字母水晶珠制成，珠子中间不用线穿过。这就意味着珠子可能在任意的地方断开。”随后，妈妈把制作方式告诉了卡卡西……卡卡西可以选择她想要的连续一段的珠子。但是做了不久她就发现了一个问题，相邻的字母水晶珠之间的连接并不是很好，可能会由于项链自身的重量而使得它断开。项链断开时情况会很糟糕。因此，断开的点很重要。如果前面是小的珠子，项链断裂的可能性要比前面是大珠子要大的多。爱动脑筋的卡卡西想要进一步测试项链的稳定性。所以他需要一个程序以便决定断开珠子的最坏的那个点。

字母水晶项链是由一串 $A =\{a_1a_2 ... a_m\}$ 序列组成，$m$ 表示制成项链的珠子的个数。当项链围成一圈时，最后一个字母 $a_m$ 就是 $a_1$ 的前驱（前一个）。第 $i$ 个珠子比第 $j$ 个珠子更容易断裂就是说序列 $a_ia_{i+1} ... a_na_1 ... a_{i-1}$ 的字典序小于序列 $a_ja_{j+1} ... a_na_1 ... a_{j-1}$ 的字典序。

序列 $a_1a_2 ... a_n$ 的字典序小于序列 $b_1b_2 ... b_n$ 的字典序就是存在一个整数 $i$，$i≤n$, 对于每个 $j(1 \leq j < i)$ 都要有 $a_j=b_j$ 且 $a_i < b_i$。聪明的你能帮助卡卡西测试出项链的稳定性，完成她的生日梦想吗？

输入格式

两行，第一行为一个正整数 $m(10≤m≤10000)$，表示组成项链的字母序长度，第二行为组成项链的字母序。每个珠子由一个英语的小写字母表示（$a-z$），$a < b ... <z$。

输出格式

一行，项链最坏连接处字母珠子的编号。例如 $i$，$A[i]$ 就是 $n$ 个可能断裂点的字典序最小的地方。如果有不止一个的解，输出最小的 $i$。

样例

11
amandamanda

11

数据范围

20% 的数据， $1≤m≤100$

40% 的数据， $1≤m≤1000$

100% 的数据， $1≤m≤10000$