// Daca se foloseste sort din stl pt n=100 000 obtinem timpi 0,340 iar daca se foloseste radixsort 0,120 :D
// Testat pe P4 3Ghz 
using namespace std;
#include <cstdio>
#include <algorithm>
#include <string>
#include <ctime>
#define maxn 100001
#define maxlg 19
struct nod{ int nr[2], p;};

char x[maxn];
nod a[maxn];
nod b[maxn];
int P[maxlg][maxn];
int n;
char *sol[maxn];
void read()
{
	freopen("sarray.in","r",stdin);
	gets(x);
	n=strlen(x);
}

struct cmp{ 
// il folosesc pt sort din stl - e mai rapid decat cu bool operator <(vezi mai jos)
	bool operator()(const nod &a,const nod &b)const
	{
		if(a.nr[0]<b.nr[0]) return 1;
		if(a.nr[0]==b.nr[0]) if(a.nr[1]<b.nr[1]) return 1;
		return 0;
	}
};
bool operator<(const nod &a, const nod &b)
// tot pt sort din stl cand nu se specifica structura... 
//nu recomand e de 1.8 ori mai lenta
{
		if(a.nr[0]<b.nr[0]) return 1;
		if(a.nr[0]==b.nr[0]) if(a.nr[1]<b.nr[1]) return 1;
		return 0;
}

inline void rad(int n, int byte,  nod a[], nod b[])
{
  int count[1024], index[1024];
  memset(count, 0, sizeof(count));
  int i;
  for(i=0;i<n;++i) ++count[(a[i].nr[0]>>byte)&1023];
  index[0]=0;
  for(i=1;i<1024;++i) index[i]=index[i-1]+count[i-1];
  for(i=0;i<n;++i) b[index[(a[i].nr[0]>>byte)&1023]++]=a[i];
}

inline void rad2(int n, int byte,  nod a[], nod b[])
{
  int count[1024], index[1024];
  memset(count, 0, sizeof(count));
  int i;
  for(i=0;i<n;++i) ++count[(a[i].nr[1]>>byte)&1023];
  index[0]=0;
  for(i=1;i<1024;++i) index[i]=index[i-1]+count[i-1];
  for(i=0;i<n;++i) b[index[(a[i].nr[1]>>byte)&1023]++]=a[i];
}


struct comp{
  bool operator()(const nod &a, const nod &b)const
  {
    if(a.nr[1]<b.nr[1]) return 1;
    return 0;
  }
};



inline void radix()
{
  rad(n, 0, a, b);// sortez in functie de primii 10 biti
  rad(n, 10, b, a);// apoi dupa urmatorii 10 biti
  
  //  rad2(n, 0, a, b);
  //rad2(n, 10, b, a);
 // mai mult nu trebuie ( pozitiile sunt <= 100 000  iar 20 biti inseamna 1 000 000)
  

  int i, p=0, nr=1;
  
  for(i=1;i<n;++i)
	   // in caz de egalitate sortez dupa nr[1]... cu sort...
	   // e mai bine decat sa trag cate un radixsort de fiecare data ... 
 
   if(a[i].nr[0]==a[i-1].nr[0])++nr;
    else 
      {
	if(nr>1) sort(a+p, a+i,comp());
	p=i;
	nr=1;
      }
   if(nr>1) sort(a+p, a+i,comp());
  
}

void sort_arrays()
{
	int i, j, cnt, stp;
	
	for(i=0;i<n;++i) P[0][i]=x[i];
	
	for(cnt=1, stp=1; cnt>>1 <n; cnt<<=1,++stp)
	{
		for(i=0;i<n;++i)
			a[i].nr[0]=P[stp-1][i],
			a[i].nr[1]=i+cnt<n?P[stp-1][i+cnt]:-1,
			a[i].p=i;
		//radix();
		sort(a,a+n, cmp());
		
		
		for(i=0;i<n;++i)
		  P[stp][a[i].p]=i>0 && a[i].nr[0]==a[i-1].nr[0] && a[i].nr[1]==a[i-1].nr[1] ? P[stp][a[i-1].p] : i;
	
	
	}
	for(i=0;i<n;++i) sol[P[stp-1][i]]=x+i;
}

void gen()
{
	n=100000;
	int i;
	//for(i=0;i<n;++i)x[i]='a';
		for(i=0;i<n;++i) x[i]=(rand()%26)+'a';
}

int main()
{
	srand(time(0));
	double s=clock();
	// read();
	gen();
	sort_arrays();
	//for(int i=0;i<n;++i) printf("%s\n", sol[i]);
		printf("%lf\n", (clock()-s)/(double)CLOCKS_PER_SEC);
	int ok=1;
	//	for(int i=1;i<n;++i) if(strcmp(sol[i-1], sol[i])>0){/*printf("%s %s\n", sol[i-1], sol[i]);*/ok=0;break;}
	printf("%d\n", ok);
	return 0;
}