Fewest letters for a suffix array

Time limit2sMemory limit512 MB

Summary

Given a permutation that is a suffix array, find the minimum number of distinct letters needed for a string that realizes exactly this suffix array.

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

Problem

The $i$ -th suffix of a string $S$ is the substring that starts at the $i$ -th letter of $S$ and runs to the end. Letters 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$ lists the suffix numbers of $S$ in the order the suffixes appear after sorting all of them lexicographically. Sorting compares the suffixes themselves, not their numbers. For example, the suffix array of $S$ = "abca" is (3, 0, 1, 2).

Several strings can share one suffix array. The suffix array (3, 0, 1, 2) comes from "abca" and also from "aaba", and "aaba" uses only two distinct letters.

You are given a suffix array of length $N$ . Among all strings $S$ whose suffix array equals the given array, find the one that uses the fewest distinct letters and report how many that is. The alphabet is unlimited.

Input

The first line contains the length $N$ of the suffix array. ( $1 \le N \le 50$ )

The second line contains the suffix array, separated by spaces. It contains every integer from 0 to $N-1$ exactly once.

Output

Print on one line the minimum number of distinct letters in a string $S$ whose suffix array is the given array.

Examples5

Example 1
Input
```
4
3 0 1 2
```
Expected output
```
2
```
Example 2
Input
```
4
3 2 1 0
```
Expected output
```
1
```
Example 3
Input
```
4
0 1 2 3
```
Expected output
```
2
```
Example 4
Input
```
10
7 4 8 6 1 5 2 9 3 0
```
Expected output
```
4
```
Example 5
Input
```
1
0
```
Expected output
```
1
```