Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline char getc()

{

	register char c = getchar();

	while(!isalpha(c))c = getchar();

	return c;

}

int n;

#define MAXN 60010

char s[MAXN];

int sa[MAXN],rnk[MAXN],height[MAXN],t1[MAXN],t2[MAXN];

int c[MAXN];

void make_SA(int n,int m)

{

	int *x = t1,*y = t2;

	int p;

	for(int i = 1;i <= m;++i)c[i] = 0;

	for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

	for(int i = 1;i <= m;++i)c[i] += c[i - 1];

	for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(int i = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		swap(x,y);

		p = 1;x[sa[1]] = 1;

		for(int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(int i = 1;i <= n;++i)

	{

		rnk[sa[i]] = i;

	}

	int k = 0;

	for(int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(j + k <= n && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)s[i] = getc();

	int tot = n;

	s[++tot] = '#';

	for(int i = n;i >= 1;--i)s[++tot] = s[i];

	make_SA(tot,256);

	int cnt = 0;

	for(int i = 1,l = 1,r = n;i <= n;++i)

	{

		if(rnk[l] < rnk[tot - r + 1])

		{

			putchar(s[l]);

			++l;

			++cnt;

		}

		else

		{

			putchar(s[r]);

			--r;

			++cnt;

		}

		if(cnt % 80 == 0)puts("");

	}

	puts("");

	return 0;

}