레이팅 미적용Lana has \(n\) pairs of shoes, labeled from 1 to \(n\). All the shoes are stored in a long
wardrobe. The shoes labeled 1 are initially at the top of the wardrobe (close to
the door), while the shoes labeled \(n\) are at the bottom (far from the door).
On the \(i\)-th of the next \(q\) days, Lana will want to wear the shoes labeled \(a_{i}\). To
retrieve a pair of shoes from the wardrobe, she first needs to remove all the pairs
that are closer to the door before she can take out the desired pair. Once she
retrieves the desired shoes, she will return other shoes to the wardrobe in the same
order as they were before. Retrieving one pair of shoes from the wardrobe takes 1 second, and returning
shoes to the wardrobe takes no additional time.
At the end of the day, Lana will take off the shoes and either:
• return them to the top of the wardrobe, or
• leave them in the hallway, if there is space available in the hallway.
The hallway can hold up to \(m\) pairs of shoes. Additionally, Lana can move any shoes from the hallway
to the top of the wardrobe at any time (except when in the process of taking out the desired pair). If the
desired pair of shoes is already in the hallway at the beginning of the day, Lana can immediately wear
them without spending any time retrieving them.
Lana is very busy and wants to minimize the total time spent retrieving shoes from the wardrobe. Help
her determine the minimum time she can spend retrieving shoes over the next \(q\) days!
The first line contains integers \(n\), \(m\) and \(q\) (\(1 \le n \le 2 \cdot 10^{5}\), \(0 \le m \le 2 \cdot 10^{5}\), \(1 \le q \le 10^{6}\)) number of shoes,
number of spaces in the hallway and number of days.
The second line contains \(q\) integers \(a_{i}\) (\(1 \le a_{i} \le n\)) shoe label that Lana wants to wear on the \(i\)-th day.
In the first and only line, output the minimum time required to retrieve the shoes in all \(q\) days.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 17점 | n, m, \(q \le 1\,000\) |
2 | 27점 | \(n = m\) |
3 | 37점 | \(m = 0\) |
4 | 24점 | \(q \le 2 \cdot 10^{5}\) |
5 | 15점 | No additional constraints. |
5 1 6
2 1 2 1 2 156 0 4
5 4 3 4173 2 7
1 2 3 2 3 1 34Clarification of the first example:
On the first day, Lana will take the shoes labeled 2 out of the wardrobe. This action will take her 2
seconds. At the end of the day, she will leave those shoes in the hallway and keep them there indefinitely.
Now, whenever she needs to retrieve the shoes labeled 1 from the wardrobe, it will take her 1 second.
However, if she needs the shoes labeled 2, she can immediately wear them from the hallway without
spending any time.
The total time she will spend retrieving shoes is: 2 + 1 + 0 + 1 + 0 + 1 = 5 seconds.