레이팅 미적용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 problem. 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.
In the first line, there are 2 positive integers \(N\) (\(1 \le N \le 10^{5}\)) and \(K\) (\(1 \le K \le 4\)) from the task
description.
In the second line, there are \(N\) postive integers \(a_{i}\) (\(1 \le a_{i} \le N\)), the numbers from the task description.
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.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | \(N \le 1000\) |
2 | 15점 | \(1 \le a_{i} \le k\) for all \(i = 1\), 2, . . . , N |
3 | 35점 | \(K = 1\) |
4 | 50점 | No additional constraints. |
3 1
1 2 166 3
6 5 6 4 5 516 2
5 4 5 2 6 55Clarification 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.