Same Suffix Array

Time limit2sMemory limit256 MB

Summary

Count the strings that differ from the given length N string in exactly one position and keep the same suffix array.

Level: Hard9 of 10
Topics: String, String matching, Sorting
Solved: No attempts yet

Problem

You are given a string of length $N$ . Count the strings that differ from it in exactly one position and have the same suffix array.

The alphabet has $M$ symbols, so each character is written as an integer from $1$ to $M$ . A larger integer comes later in lexicographic order.

The suffix array of a string $S$ of length $N$ is built by sorting the $N$ suffixes of $S$ in lexicographic order and listing the starting position of each suffix in that order.

Input

The first line contains $N$ and $M$ , separated by a space ( $1 \le N, M \le 500\,000$ ). $N$ is the length of the string and $M$ is the number of symbols in the alphabet.

The second line contains $N$ integers, the characters of the string in order, separated by spaces. Each integer is between $1$ and $M$ .

Output

Print the number of strings that differ from the given string in exactly one position and have the same suffix array.

Hint

In the first example, 2 1 is the only string that satisfies the condition.

Examples3

Example 1
Input
```
2 2
1 1
```
Expected output
```
1
```
Example 2
Input
```
5 3
1 2 1 3 2
```
Expected output
```
2
```
Example 3
Input
```
1 5
3
```
Expected output
```
4
```