Učiteljica

Time limit5sMemory limit1024 MB

Summary

Count the ways to delete some prefix and suffix so that, for each i from 1 to K (K at most 4), some value appears exactly i times in what remains.

Level: Medium6 of 10
Topics: Sliding window, Two pointers, Hash map, Array
Solved: No attempts yet

Problem

In the best school in Varaždin, the computer science teacher Lana often gave her students impossible or unsolvable problems. Each student had to solve only one problem during the school year to pass with an excellent grade. Students who solved none by the end of the year had to repeat the grade.

On the last day of school, she wrote this problem on the board. You have a sequence of $N$ numbers. You may remove some elements from the beginning, from the end, or from both. How many ways can you do this so that, after the removal, for every $i$ from 1 to $K$ , at least one number appears exactly $i$ times in the remaining sequence?

Fran, a student who had not solved any problems yet, said he knew how to solve it. He cannot code, so he asks you to write a program that solves this problem.

Input

The first line contains two positive integers $N$ (1 ≤ $N$ ≤ 10^5) and $K$ (1 ≤ $K$ ≤ 4).

The second line contains $N$ positive integers $a_i$ (1 ≤ $a_i$ ≤ $N$ ), the elements of the sequence.

Output

Print one integer, the number of distinct deletions that satisfy the condition. Two deletions are different if some index is deleted in one of them and not deleted in the other.

Examples3

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