Heidi and Library (medium)

10000ms

262144K

Description:

Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.

Input:

Same as the easy version, but the limits have changed: 1 ≤ n, k ≤ 400 000.

Output:

Same as the easy version.

Sample Input:

4 100
1 2 2 1

Sample Output:

Sample Input:

4 1
1 2 2 1

Sample Output:

Sample Input:

4 2
1 2 3 1

Sample Output:

Informação

Provedor Codeforces

Código CF802B