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

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

struct SuffixArray {
    vector<int> sa, lcp;
	vector<int> sort_cyclic_shifts(string const& s) {
	    int n = s.size();
	    const int alphabet = 256;
	    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
	    for (int i = 0; i < n; i++)
	        cnt[s[i]]++;
	    for (int i = 1; i < alphabet; i++)
	        cnt[i] += cnt[i-1];
	    for (int i = 0; i < n; i++)
	        p[--cnt[s[i]]] = i;
	    c[p[0]] = 0;
	    int classes = 1;
	    for (int i = 1; i < n; i++) {
	        if (s[p[i]] != s[p[i-1]])
	            classes++;
	        c[p[i]] = classes - 1;
	    }
	    vector<int> pn(n), cn(n);
	    for (int h = 0; (1 << h) < n; ++h) {
	        for (int i = 0; i < n; i++) {
	            pn[i] = p[i] - (1 << h);
	            if (pn[i] < 0)
	                pn[i] += n;
	        }
	        fill(cnt.begin(), cnt.begin() + classes, 0);
	        for (int i = 0; i < n; i++)
	            cnt[c[pn[i]]]++;
	        for (int i = 1; i < classes; i++)
	            cnt[i] += cnt[i-1];
	        for (int i = n-1; i >= 0; i--)
	            p[--cnt[c[pn[i]]]] = pn[i];
	        cn[p[0]] = 0;
	        classes = 1;
	        for (int i = 1; i < n; i++) {
	            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
	            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
	            if (cur != prev)
	                ++classes;
	            cn[p[i]] = classes - 1;
	        }
	        c.swap(cn);
	    }
	    return p;
	}

	vector<int> lcp_construction(string const& s) {
	    int n = s.size();
	    vector<int> rank(n, 0);
	    for (int i = 0; i < n; i++)
	        rank[sa[i]] = i;

	    int k = 0;

	    //kasai, modified a bit for circular rotations
	    vector<int> lcp(n, 0);
	    for (int i = 0; i < n; i++) {
	        if (rank[i] == n - 1) {
	        	//if first suffix and last suffix start with same char, string is a repeated single char
	        	k = s[sa[0]]==s[i]?n:0;
	        }else{
		        int j = sa[rank[i] + 1];
		        while (k < n && s[(i+k)%n] == s[(j+k)%n])
		            k++;
	        }
	        lcp[rank[i]] = k;
	        if (k)
	            k--;
	    }
	    return lcp;
	}

    SuffixArray(const string &s) {
        sa = sort_cyclic_shifts(s);
        lcp = lcp_construction(s);
    }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    int n;
    cin>>n;
    string s(n,0);
    vector<int> vec(n);
    for(int i=0;i<n;++i){
    	cin>>vec[i];
    }

    for(int i=0;i<n;++i){
    	s[i]=vec[i]<vec[(i+1)%n]?'a':'b';
    }

    SuffixArray sa(s);

	vector<int> ans(n);
    for (int i=0;i<n;++i) {
    	int x = max(sa.lcp[i],sa.lcp[(i+n-1)%n])+1;
    	ans[sa.sa[i]]=x<=n ? x : -1;
    }
	for(int i = 0;i<n;++i){
		cout<<ans[i]<<endl;
	}
    return 0;
}