配点 : 100 点
問題文
在 JOI 市场 K 不同类型的马卡龙已发布。这些马卡龙是盒装出售的。
包装马卡龙时,N 马卡龙在盒子里从左到右排成一排。 i 個目 (1 \leqq i \leqq N) 处的马卡龙类型是 A_i 。
Bitaro买了一盒马卡龙。
Vivako 的目标也是马卡龙。 Bitaro 不想让 Vibako 吃他的马卡龙,因此他穿过了一系列高楼。 1 我们决定在一个部分上放一张纸,并使该部分中的马卡龙不可见。从左边开始 l 从左开始,从马卡龙开始 r 将纸张放入马卡龙 (1 \leqq l \leqq r \leqq N),纸张的长度为 r - l + 1 。
Vivako 是 K如果您看不到所有类型的马卡龙,请勿尝试包装它们。
Vitaro 希望通过将纸张尽可能短来阻止 Vivako 试图包装马卡龙。给定马卡龙盒子的信息,编写一个程序,找出 Bitaro 需要拉伸的纸张的最小长度。
入力
输入是按以下格式从标准输入给出的。
N K A_1 A_2 \cdots A_N
出力
Bitaro 需要拉伸的纸张的最小长度被写入标准输出。 输出为 1 行。但是,如果不需要拉伸板材 输出 0 。
制約
- 1 \leqq K \leqq N \leqq 500\,000.
- 1 \leqq A_i \leqq K (1 \leqq i \leqq N).
- 所有输入值都是整数。
小課題
- (20 点) N \leqq 100.
- (30 点) K \leqq 100.
- (50 点)没有额外的限制。
入力例 1
7 3 1 3 2 3 1 2 3
出力例 1
4
例如,从左开始 3 来自项目 6 调整长度以使马卡龙不可见。 当您拉伸 4 纸时,您可以看到不同的类型。 2 的马卡龙是 1 Vivako 不碰马卡龙的盒子,因为她始终看不到它们。
有了比这更短的纸,不可能阻止 Vivako 尝试包装马卡龙。因此,4 。 你只需要砍掉
此输入示例满足所有子任务约束。
入力例 2
7 4 1 3 4 4 1 3 1
出力例 2
0
Bitaro购买的马卡龙从一开始就有不同类型的包装。 由于没有 2 马卡龙,Vivako 不必担心包装马卡龙,即使她不需要用床单覆盖它们。
因此,0 。 你只需要砍掉
此输入示例满足所有子任务约束。