[R65B]卡片 - 代码源竞赛平台

时空限制

1S/512M

题目描述

有 $n$ 张卡片围成一圈，第 $i$ 张卡片上写着整数 $a_i$。

请你找到一个起点 $s$（$1 \le s \le n$），使得从第 $s$ 张卡片开始，连续取 $k$ 张卡片后，得到的这 $k$ 个数恰好是 $1, 2, \dots, k$ 的一个排列$^\ddagger$。

如果存在多个满足条件的起点，输出最小的 $s$。如果不存在，输出 $-1$。

卡片编号为 $1$ 到 $n$。因为卡片围成一圈，所以第 $n$ 张卡片的下一张是第 $1$ 张。

排列$^\ddagger$：$1, 2, \dots, k$ 的一个排列是指一个长度为 $k$ 的序列，其中 $1$ 到 $k$ 的每个正整数都恰好出现一次。

格式

输入格式

第一行包含两个正整数 $n$ 和 $k$，表示卡片数量和需要选取的连续卡片张数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每张卡片上的整数。

输出格式

输出一个整数，表示满足条件的最小起点 $s$。若不存在，则输出 $-1$。

样例

样例输入 #1

5 3
2 4 1 3 2

样例输出 #1

3

样例解释 #1

从第 $3$ 张卡片开始顺时针连续取 $3$ 张，得到的数字依次为 $1, 3, 2$，这三个数恰好是 $1, 2, 3$ 的一个排列。因此输出起点 $3$。

样例输入 #2

4 2
3 1 3 2

样例输出 #2

-1

样例解释 #2

不存在连续的 $2$ 张卡片能够恰好组成 $1, 2$ 的排列。

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，$1 \le k \le n \le 1000$，$1 \le a_i \le 1000$。