QaGEhB - Online C++0x Compiler & Debugging Tool

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll mx=200001;
ll sa[mx],lcp[mx],pos[mx],tmp[mx];
char a[mx];
ll d=1,n;
bool cmp(ll x,ll y){
    if(pos[x]!=pos[y]) return pos[x]<pos[y];
    x+=d;y+=d;
    return pos[x%n]<pos[y%n];//x<n&&y<n?pos[x]<pos[y]:x>y for non-circular
}
void findSA(){
    for(ll i=0;i<n;++i){
        sa[i]=i;
        pos[i]=a[i];
    }
    for(d=1;;d<<=1){
    	sort(sa,sa+n,cmp);
        tmp[0]=0;
        for(ll i=1;i<n;++i) tmp[i]=tmp[i-1]+cmp(sa[i-1],sa[i]);
        for(ll i=0;i<n;++i) pos[sa[i]]=tmp[i];
        if(tmp[n-1]==n-1 || d>=n) break;
    }
}
void findLCP(){
    ll rank[mx];//non-circular may just use pos (suffixes are unique)
    for(ll i=0;i<n;++i) rank[sa[i]]=i;
    for(ll i=0, k=0;i<n;++i){
        if(rank[i]<n-1) for(ll j=sa[rank[i]+1];k<n&&a[(i+k)%n]==a[(j+k)%n];++k);//non-circular: for(ll j=sa[rank[i]+1];i+k<n&&j+k<n&&a[i]==a[j];++k);
        else k = a[sa[0]]==a[i]?n:0;//remove this for non-circular
        lcp[rank[i]]=k;
        k=k-1>0?k-1:0;
    }
}
int a1[mx];
int ans[mx];
int main(){
    scanf("%d",&n);
    for(ll i=0;i<n;++i) scanf("%d",a1+i);
    for(ll i=0;i<n;++i) a[i]=(a1[i]<a1[(i+1)%n]?'a':'b');
    findSA();
    findLCP();
    for (ll i=0;i<n;++i) {
    	ll x = max(lcp[i],lcp[(i+n-1)%n])+1;
    	ans[sa[i]] = x <= n ? x : -1;
    }
    for(ll i=0;i<n;++i) printf("%d\n",ans[i]);
    return 0;
}