Minimal Shoe Retrieval Time

You are given \(n\) pairs of shoes numbered from \(1\) to \(n\). Initially, the shoes are placed in a shoe cabinet that is organized as a stack; from the top to the bottom the shoes are arranged as \(1,2,\ldots,n\) (with shoe \(1\) at the top).

Over the next \(q\) days, on day \(i\) you need to wear the shoe with label \(a_i\). The retrieval process is as follows:

• If the required shoe is in the stack and it is the \(j\)-th shoe from the top (i.e. counting from 1), it takes exactly \(j\) seconds to take it out. When taking a shoe from the stack, its relative order does not affect the shoes above it.
• If the shoe is already in the corridor then no time is needed.

At the end of each day immediately after using the shoe \(a_i\), you have a choice: you can either push (i.e. return) the shoe into the stack or leave it in the corridor. However, the corridor can hold at most \(m\) pairs of shoes.

Extra operation: At any time (except during the retrieval process) you may take any number of shoes from the corridor and push them back onto the stack in any order you wish. Since you know the entire sequence of requests in advance you can plan these operations optimally.

Your task is to minimize the total time spent in retrieving shoes.

Note: When a shoe is retrieved from the stack, if you choose to leave it in the corridor then subsequent usages (before it is forced back into the stack) cost \(0\) seconds. However, if the corridor is full at the end of a day, you are forced to reinsert all shoes from the corridor (at no time cost) into the stack in an order of your choosing before placing the just retrieved shoe into the corridor.

The optimal strategy involves delaying the re‐insertion from the corridor until the corridor is full, and then reordering the reinserted shoes (using future usage information) to minimize the retrieval costs in subsequent days.

In summary, given \(n, m, q\) and the sequence \(a_1,a_2,\ldots,a_q\), compute the minimal total time required to retrieve the shoes over \(q\) days.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) \((1 \le m \le n)\) — the number of pairs of shoes, the maximum number of shoes that can be left in the corridor, and the number of days (queries), respectively.

The second line contains \(q\) integers \(a_1,a_2,\ldots,a_q\) \((1 \le a_i \le n)\) where \(a_i\) is the shoe you need on day \(i\).

outputFormat

Output a single integer — the minimal total time (in seconds) required to retrieve the shoes over \(q\) days.

sample

3 1 3
2 1 2

4