Suffix Array 1

Time limit2sMemory limit512 MB

Summary

Given S, decide whether some lexicographically smaller string of the same length has an identical suffix array. Constraints: |S| <= 50.

Level: Medium7 of 10
Topics: String, Sorting, Greedy
Solved: No attempts yet

Problem

The $i$ -th suffix of a string $S$ is the part of $S$ that starts at position $i$ and runs to the end of the string. Positions are numbered from 0. For example, if $S$ = "abcde", the 0th suffix is "abcde" and the 3rd suffix is "de".

The suffix array of $S$ is built by sorting all suffixes of $S$ in lexicographic order and then writing down the starting position of each suffix in that order. For example, if $S$ = "abca", the suffix array is $(3, 0, 1, 2)$ .

Given a string $S$ , write a program that decides whether a string $T$ exists that has the same suffix array as $S$ and comes before $S$ in lexicographic order. $T$ has the same length as $S$ , and $T$ also consists of lowercase letters only.

Input

The first line contains the string $S$ . The length of $S$ is between 1 and 50, and $S$ consists of lowercase letters only.

Output

Print 1 if a string exists that comes before $S$ in lexicographic order and has the same suffix array as $S$ . Otherwise print 0.

Examples3

Example 1
Input
```
abca
```
Expected output
```
1
```
Example 2
Input
```
bbbb
```
Expected output
```
1
```
Example 3
Input
```
aaaa
```
Expected output
```
0
```