题意

给定一个环，从任意一个点出发形成一个串，求这个串的最小字典序

思路

O(n)做法最小表示法，不会，再见

按照处理环的套路，先倍长了再说

---

后缀数组SA

显然就是求最小的后缀，但是要注意这个后缀长度必须不小于n，后缀排序裸题（因为数据过水所以不需要离散化）

---

后缀自动机SAM

（据说这道题被卡了但还是提一下）

对倍长后的串建SAM之后，从root向下走最小的边走n次即可

Code;

#include
    
     #define N 600005using namespace std;int n,m,len,a[N],sa[N],rk[N],tp[N],h[N],cnt[N];template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;}void radix_sort(){    for(int i=0;i<=m;++i) cnt[i]=0;    for(int i=1;i<=len;++i) cnt[rk[i]]++;    for(int i=1;i<=m;++i) cnt[i]+=cnt[i-1];    for(int i=len;i>=1;--i) sa[cnt[rk[tp[i]]]--]=tp[i];}void get_sa(){    m=200;    for(int i=1;i<=len;++i) rk[i]=a[i],tp[i]=i;    radix_sort();    for(int t=1;t
      
       <<=1)    {        int p=0;        for(int i=1;i<=t;++i) tp[++p]=len-t+i;        for(int i=1;i<=len;++i) if(sa[i]>t) tp[++p]=sa[i]-t;        radix_sort();        swap(rk,tp);        rk[sa[1]]=p=1;        for(int i=2;i<=len;++i) rk[sa[i]]=(tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+t]==tp[sa[i-1]+t]) ? p : ++p;        if(p==len) break;        m=p;    }}void get_h()//可以不要qwq{    int ht=0;    for(int i=1;i<=len;++i) rk[sa[i]]=i;    for(int i=1;i<=len;++i)    {        int p=sa[rk[i]-1];        while(a[i+ht]==a[p+ht]) ++ht;        h[rk[i]]=ht;        ht=max(0,ht-1);    }}int main(){    read(n);len=n*2;    for(int i=1;i<=n;++i) read(a[i]),a[i+n]=a[i];    get_sa();    get_h();    int con=0,ans=len+1;    for(int i=1;i<=len;++i)    {        if(con&&h[i]