uciteljica (COCI CONTEST_#1)
Time limit: 5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: segment tree, inclusion-exclusion

# Task Učiteljica

In the best school in Varaždin, there was an excellent computer science teacher known for her interesting and unusual ideas. Her name was Lana, and she often gave her students impossible or unsolvable problems. Each student only needed to solve 1 problem during the school year to pass the class with an excellent grade. Students who did not solve any tasks by the end of the year would have to repeat the grade. On the last day of school, she wrote an extremely difficult problem on the board, which went as follows:

Imagine you have a sequence of numbers of length $N$, and you can remove some elements from the beginning or the end (or both). How many ways can you perform such deletions so that after the deletion, there must be at least 1 number that appears exactly once, at least 1 number that appears exactly twice, and at least 1 number that appears exactly $K$ times.

A student named Fran, who had not solved any problems so far, quickly said, "I know how to solve this problem." Teacher Lana did not believe Fran and told him, "Write the code in the next 30 minutes, and then I'll believe you. If you don't, you'll have to repeat the grade." Fran doesn't know how to code, so he urgently asked for your help to write the code to solve this task. In his hurry, he forgot to explain his idea for solving the task. Write a code that takes as input the numbers $N$ and $K$, the sequence of $N$ elements, and solve Lana's question to help Fran.

## Input

In the first line, there are 2 positive integers $N$ ($1 \le N \le 10^5$) and $K$ ($1 < K < 4$) from the task description.

In the second line, there are $N$ positive integers $a_i$ ($1 \le a_i \le N$), the numbers from the task description.

## Output

In the first line, print a whole number, the number of distinct deletions such that the conditions from the task hold. Two deletions are different if there is an index that is not deleted in one, but deleted in the other.

## Scoring

| Subtask | Points | Constraints                                   |
|---------|--------|-----------------------------------------------|
| 1       | 20     | $N \le 1000$                                  |
| 2       | 15     | $1 \le a_i \le k \text{ for all } i = 1, 2, ..., N$ |
| 3       | 35     | $K = 1$                                       |
| 4       | 50     | No additional constraints.                    |

## Examples

| Input        | Input              | Input              |
|--------------|--------------------|--------------------|
| `3 1`<br>`1 2 1` | `6 3`<br>`6 5 6 4 5 5` | `6 2`<br>`5 4 5 2 6 5` |
| Output       | Output             | Output             |
| `6`            | `1`                  | `5`                  |

#### Clarification of the first example:

The possible sequences after deletion are: [1], [2], [1], [1, 2], [2, 1], [1, 2, 1], and in each of the 6 sequences, there is a number that appears exactly once.

#### Clarification of the second example:

The only sequence after deletion in which there is at least 1 number that appears exactly once, at least 1 number that appears exactly twice, and at least 1 number that appears exactly three times is the given sequence of $N$ numbers.

Starter code:

Grader code:

Setup script:

Evaluation script: