#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <set>
#include <limits>
using namespace std;

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define F(i, n) for(int (i)=0;(i)<(n);++(i))
#define REP(i, s, t) for(int (i)=(s);(i)<=(t);++(i))
#define UREP(i, s, t) for(int (i)=(s);(i)>=(t);--(i))
#define REPOK(i, s, t, o) for(int (i)=(s);(i)<=(t) && (o);++(i))

#define MAXN 100000
#define MAXM 10000
#define MOD 10000007

#define PI 3.1415926535897932384626433832795
#define HALF_PI 1.5707963267948966192313216916398

typedef long long LL;

const double maxdouble = numeric_limits<double>::max();
const double eps = 1e-10;
const int INF = 0x7FFFFFFF;

int n, k;
const int maxn = 200000;
int sa[maxn*2+5];
int _rank[maxn*2+5];
int tmp[maxn*2+5];
int _c[maxn*2+5];

int compare_sa(const void * a, const void * b) {
	int i = *(int*)a;
	int j = *(int*)b;
	if (_rank[i] != _rank[j]) {
		if ( _rank[i] < _rank[j])
			return -1;
		else if (_rank[i] > _rank[j])
			return 1;
		else
			return 0;
	} else {
		int ri = i + k <= n ? _rank[i+k] : -INF;
		int rj = j + k <= n ? _rank[j+k] : -INF;
		if ( ri < rj)
			return -1;
		else if (ri > rj)
			return 1;
		else
			return 0;
	}
}
/*
  void construct_sa(int *S, int len) {
  int m = len;
  n = len;
  for (int i=0;i<=n;++i) {
  sa[i] = i;
  _rank[i] = i < n ? S[i] : -INF;
  }
  // 在字符串最后多加了一个最小的字符，值为-INF
  k = 1;
  qsort(sa, n+1, sizeof(int), compare_sa);
  // 在tmp中临时存_rank的新值
  // 相同的后缀排名一样
  tmp[sa[0]] = 0;
  for (int i=1;i<=n;++i)
  //tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
  tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(&sa[i-1], &sa[i])<0 ? 1 : 0);
  for (int i=0;i<=n;++i)
  _rank[i] = tmp[i];
  for (k=2;k<=n;k*=2) {
  // 先按照第二关键字排序
  int p = 0;
  for (int i=n-k+1;i<=n;++i) tmp[p++] = i;
  for (int i=0;i<=n;++i) if (sa[i] >= k) tmp[p++] = sa[i]-k;
  // 按第一关键字排序
  for (int i=0;i<=m;++i) _c[i] = 0;
  for (int i=0;i<=n;++i) _c[_rank[tmp[i]]]++;
  for (int i=1;i<=m;++i) _c[i]+=_c[i-1];
  for (int i=n;i>=0;--i) sa[--_c[_rank[tmp[i]]]] = tmp[i];
  // 在tmp中临时存_rank的新值
  // 相同的后缀排名一样
  tmp[sa[0]] = 0;
  for (int i=1;i<=n;++i)
  tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(&sa[i-1], &sa[i])<0 ? 1 : 0);
  for (int i=0;i<=n;++i)
  _rank[i] = tmp[i];
  m = _rank[sa[n]];
  if (m >= n)
  break;
  }
  }*/
void construct_sa(int *S, int len) {
	int m = len;
	n = len;
	
	for (int i=0;i<=n;++i) {
		sa[i] = i;
		_rank[i] = i < n ? S[i] : -INF;
	}// 在字符串最后多加了一个最小的字符，值为-INF
	k = 1;
	qsort(sa, n+1, sizeof(int), compare_sa);
	tmp[sa[0]] = 0;
	for (int i=1;i<=n;++i)
		tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(&sa[i-1], &sa[i])<0 ? 1 : 0);
	for (int i=0;i<=n;++i)
		_rank[i] = tmp[i];
	int *x = _rank, *y = tmp;
	for (k=2;k<=n;k*=2) {
		// 所要排序的元素i是后缀下标 i对应子序列S[i...i+2*k-1]
		// 对于sa[i]-k来说 i是second key, _rank[sa[i]-k]是first key
		// 先按照第二关键字排序
		int p = 0;
		for (int i=n-k+1;i<=n;++i) y[p++] = i;
		for (int i=0;i<=n;++i) if (sa[i] >= k) y[p++] = sa[i]-k;
		// 按第一关键字排序
		for (int i=0;i<=m;++i) _c[i] = 0;
		for (int i=0;i<=n;++i) _c[x[y[i]]]++;
		for (int i=1;i<=m;++i) _c[i]+=_c[i-1];
		for (int i=n;i>=0;--i) sa[--_c[x[y[i]]]] = y[i];
		swap(x, y);
		p = 1;x[sa[0]] = 0;
		for (int i=1;i<=n;++i) {
			bool inc = true;
			int _i = sa[i], _j = sa[i-1];
			if (y[_i] == y[_j]) {
				int ri = _i + k <= n ? y[_i+k] : -INF;
				int rj = _j + k <= n ? y[_j+k] : -INF;
				if (ri == rj)
					inc = false;
			}
			if (inc)
				x[sa[i]] = p++;
			else
				x[sa[i]] = p-1;
		}
		if (p >= n)
			break;
		m = p;
	}
}

int _buf[maxn + 5];
int rev[maxn*2 + 5];
int main() {
	//freopen("input.in", "r", stdin);
	
	int N, tmp, len;
	scanf("%d",&N);
	
	REP(i, 0, N-1) {
		scanf("%d",&_buf[i]);
	}
	
	int len_rev = N-2;
	REP(i, 0, len_rev-1) {
		rev[i] = _buf[i];
	}
	reverse(rev, rev+len_rev);
	construct_sa(rev, len_rev);
	int pos1 = sa[1];
	len = (N-2-sa[1]);
	REP(i, 0, len-1) {
		printf("%d\n",rev[sa[1]+i]);
	}
	len = N - len;
	REP(i, 0, len-1) {
		rev[i] = _buf[N-len+i];
	}
	REP(i, 0, len-1) {
		rev[i+len] = rev[i];
	}
	len *= 2;
	reverse(rev, rev+len);
	construct_sa(rev, len);
	for(pos1=0;pos1<=len;++pos1)
		if (len - sa[pos1] > len/2 && sa[pos1]) {
			REP(i, 0, len/2-1) {
				printf("%d\n", rev[sa[pos1]+i]);
			}
			break;
		}
	return 0;
}

由于第一个元素最大，所以第一段子序列和其他子序列不相关。直接将原序列倒序后求后缀数组。求第二段与第三段子序列可以用下面的方法。

acbca 对于一段序列s

acbcaacbca拓展为序列2s

acb ca -> bca acs分为划分子序列s1, s2， 然后各自倒序得到s'

ac{bcaac}bca将2s倒序后可以发现 s' 是2s的一个子序列

所以可以直接将剩下的序列逆序后求suffix array， 然后取合适的一串子序列。

POJ上这道题排序直接用qsort会TLE。所以用来LRJ给出的基数排序代码，由于元素范围没有给出，第一趟排序用qsort。