AT_tupc2023_i.Maximize Array

给定一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\ldots,A_N)$，以及一个正整数 $K$。你可以对 $A$ 进行如下操作任意次：

• 删除 $A$ 的一个长度为 $K$ 的连续子序列。具体来说，设当前 $A$ 的长度为 $M$，你可以选择一个整数 $i\ (1\leq i\leq M-K+1)$，并将 $A=(A_1,\ldots,A_M)$ 替换为 $A=(A_1,\ldots,A_{i-1},A_{i+K},\ldots,A_{M})$。

请问，经过若干次操作后，能得到的字典序最大的序列是什么？

输入从标准输入中给出，格式如下：

$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_N$

输出答案。

样例解释 1

得到字典序最大序列的一个操作步骤如下：

• $(1,2,3,4,\color{red}{1}\color{black},\color{red}{2}\color{black},\color{red}{3}\color{black},4,1)\to(\color{red}{1}\color{black},\color{red}{2}\color{black},\color{red}{3}\color{black},4,4,1) \to (4,4,1)$

样例解释 2

得到字典序最大序列的一个操作步骤如下：

• $(1,6,4,\color{red}{2}\color{black},3,5)\to(1,6,\color{red}{4}\color{black},3,5) \to (\color{red}{1}\color{black},6,3,5) \to (6,\color{red}{3}\color{black},5) \to (6,5)$

样例解释 3

一次操作也不做是最优的。

数据范围

• $2\leq N\leq 3\times 10^5$
• $1\leq K\leq N-1$
• $1\leq A_{i}\leq N$
• 输入均为整数。

由 ChatGPT 5 翻译