{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003e小象和他在利沃夫动物园的朋友们从派对上回来。但突然间,他们被名叫大河马的警察拦住了,他想对大象们进行酒精测试。\u003c/p\u003e\n\n\u003cp\u003e大象们按从左到右的顺序排成一排,编号从 \u003cb\u003e0\u003c/b\u003e 到 \u003cb\u003eN-1\u003c/b\u003e。设 \u003cb\u003eR[i]\u003c/b\u003e 为第 \u003cb\u003ei\u003c/b\u003e 只大象的呼吸测试结果。\u003c/p\u003e\n\n\u003cp\u003e根据动物园的现行法律,如果它们中存在 \u003cb\u003eK\u003c/b\u003e 只连续的大象,其中至少有 \u003cb\u003eM\u003c/b\u003e 只大象的测试结果是这 \u003cb\u003eK\u003c/b\u003e 只大象中的最大值,那么它们将被逮捕。\u003c/p\u003e\n\n\u003cp\u003e用简陋的数学符号表示,我们可以这样定义:如果存在 \u003cb\u003ei\u003c/b\u003e 从 \u003cb\u003e0\u003c/b\u003e 到 \u003cb\u003eN-K\u003c/b\u003e(包括)之间的值,使得在 \u003cb\u003ei\u003c/b\u003e 到 \u003cb\u003ei+K-1\u003c/b\u003e(包括)之间至少有 \u003cb\u003eM\u003c/b\u003e 个不同的 \u003cb\u003ej\u003c/b\u003e 值,满足 \u003cb\u003eR[j] \u003d max{R[i], R[i+1], ..., R[i+K-1]}\u003c/b\u003e。\u003c/p\u003e\n\n\u003cp\u003e大河马很老了,小象可以改变一些测试结果。在一次操作中,他可以给任何一只大象的测试结果加 \u003cb\u003e1\u003c/b\u003e。但对于每只大象,他最多只能应用这个操作一次。\u003c/p\u003e\n\n\u003cp\u003e小象需要应用多少次操作,才能使得在应用所有操作后,大象们避免被逮捕?如果无论应用多少次操作都无法避免被逮捕,则输出 \u003cb\u003e-1\u003c/b\u003e。\u003c/p\u003e\n\n\u003ch3\u003e输入\u003c/h3\u003e\n\u003cp\u003e输入的第一行包含一个整数 \u003cb\u003eT\u003c/b\u003e,表示测试用例的数量。接下来是 \u003cb\u003eT\u003c/b\u003e 个测试用例的描述。每个测试用例的第一行包含三个用空格分隔的整数 \u003cb\u003eN, K, M\u003c/b\u003e。第二行包含 \u003cb\u003eN\u003c/b\u003e 个用空格分隔的整数 \u003cb\u003eR[0], R[1], ..., R[N-1]\u003c/b\u003e,表示大象们的测试结果。\u003c/p\u003e\n\n\u003ch3\u003e输出\u003c/h3\u003e\n\u003cp\u003e对于每个测试用例,输出一行,包含避免被逮捕所需的最少操作次数。\u003c/p\u003e\n\n\u003ch3\u003e约束\u003c/h3\u003e\n\u003cul\u003e\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e10\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eM\u003c/b\u003e ≤ \u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ \u003cb\u003e17\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eR[i]\u003c/b\u003e ≤ \u003cb\u003e17\u003c/b\u003e\u003c/li\u003e\u003c/ul\u003e"}},{"title":"示例 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n5 3 2\n1 3 1 2 1\n5 3 3\n7 7 7 7 7\n5 3 3\n7 7 7 8 8\n4 3 1\n1 3 1 2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n1\n1\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e\u003cb\u003e示例 1.\u003c/b\u003e 让我们遵循避免逮捕的简陋数学定义。我们将考虑所有 \u003cb\u003ei\u003c/b\u003e 从 \u003cb\u003e0\u003c/b\u003e 到 \u003cb\u003eN-K \u003d 2\u003c/b\u003e(包括)的值,并应该计算定义中描述的 \u003cb\u003ej\u003c/b\u003e 值的数量。如果小于 \u003cb\u003eM \u003d 2\u003c/b\u003e,则这个 \u003cb\u003ei\u003c/b\u003e 值不会导致逮捕,否则会导致。\u003c/p\u003e\n\u003ctable width\u003d\"100%\" border\u003d\"1\" cellspacing\u003d\"0\"\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e对于 \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e 我们有 \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e结论\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d0\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{1, 3, 1}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 3\u003c/b\u003e 对于 \u003cb\u003ej \u003d 1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{3, 1, 2}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 3\u003c/b\u003e 对于 \u003cb\u003ej \u003d 1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{1, 2, 1}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 2\u003c/b\u003e 对于 \u003cb\u003ej \u003d 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003e所以我们看到大象们的初始测试结果不会导致它们被逮捕。因此,小象不需要应用任何操作。因此,答案是 0。\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e示例 2.\u003c/b\u003e我们有 \u003cb\u003eN \u003d 5\u003c/b\u003e,\u003cb\u003eK \u003d 3\u003c/b\u003e,\u003cb\u003eM \u003d 3\u003c/b\u003e。让我们构建类似于示例 1 的表格。这里,如果我们在定义中至少有 \u003cb\u003e3\u003c/b\u003e 个 \u003cb\u003ej\u003c/b\u003e 值,则 \u003cb\u003ei\u003c/b\u003e 的值将导致逮捕。\u003c/p\u003e\n\u003ctable width\u003d\"100%\" border\u003d\"1\" cellspacing\u003d\"0\"\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e对于 \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e 我们有 \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e结论\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d0\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 7, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 7\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 7\u003c/b\u003e 对于 \u003cb\u003ej \u003d 0, 1, 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 7, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 7\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 7\u003c/b\u003e 对于 \u003cb\u003ej \u003d 1, 2, 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 7, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 7\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 7\u003c/b\u003e 对于 \u003cb\u003ej \u003d 2, 3, 4\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003e所以我们看到对于大象们的初始测试结果,每个 \u003cb\u003ei\u003c/b\u003e 的值都会导致它们被逮捕。因此,小象需要应用一些操作以避免逮捕。他可以通过给结果 \u003cb\u003eR[2]\u003c/b\u003e 加 \u003cb\u003e1\u003c/b\u003e 来实现目标。然后结果将变为 \u003cb\u003e{R[0], R[1], R[2], R[3], R[4]} \u003d {7, 7, 8, 7, 7}\u003c/b\u003e。现在让我们检查一下,现在大象们不会被逮捕。\u003c/p\u003e\n\u003ctable width\u003d\"100%\" border\u003d\"1\" cellspacing\u003d\"0\"\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e对于 \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e 我们有 \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e结论\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d0\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 7, 8}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 8, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{8, 7, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003e所以我们看到现在大象们的测试结果不会导致它们被逮捕。因此我们看到使用 0 次操作无法避免逮捕,但使用 1 次操作可以。因此答案是 1。\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e示例 3.\u003c/b\u003e我们有 \u003cb\u003eN \u003d 5\u003c/b\u003e,\u003cb\u003eK \u003d 3\u003c/b\u003e,\u003cb\u003eM \u003d 3\u003c/b\u003e。让我们构建类似于示例 1 的表格。这里,如果我们在定义中至少有 \u003cb\u003e3\u003c/b\u003e 个 \u003cb\u003ej\u003c/b\u003e 值,则 \u003cb\u003ei\u003c/b\u003e 的值将导致逮捕。\u003c/p\u003e\n\u003ctable width\u003d\"100%\" border\u003d\"1\" cellspacing\u003d\"0\"\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e对于 \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e 我们有 \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e结论\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d0\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 7, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 7\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 7\u003c/b\u003e 对于 \u003cb\u003ej \u003d 0, 1, 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 7, 8}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 8, 8}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 3, 4\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003e所以我们看到对于大象们的初始测试结果,值为 \u003cb\u003ei \u003d 0\u003c/b\u003e 的情况将导致它们被逮捕。因此,小象需要应用一些操作以避免逮捕。他可以通过给结果 \u003cb\u003eR[1]\u003c/b\u003e 加 \u003cb\u003e1\u003c/b\u003e 来实现目标。然后结果将变为 \u003cb\u003e{R[0], R[1], R[2], R[3], R[4]} \u003d {7, 8, 7, 8, 8}\u003c/b\u003e。现在让我们检查一下,现在大象们不会被逮捕。\u003c/p\u003e\n\u003ctable width\u003d\"100%\" border\u003d\"1\" cellspacing\u003d\"0\"\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax{R[i],...,R[i+K-1]}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e对于 \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e 我们有 \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e结论\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d0\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 8, 7}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{8, 7, 8}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 1, 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003ctr\u003e\u003ctd\u003e\u003cb\u003ei\u003d2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003e{7, 8, 8}\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003emax \u003d 8\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e\u003cb\u003eR[j] \u003d 8\u003c/b\u003e 对于 \u003cb\u003ej \u003d 3, 4\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003e不会导致逮捕\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003e所以我们看到现在大象们的测试结果不会导致它们被逮捕。因此我们看到使用 0 次操作无法避免逮捕,但使用 1 次操作可以。请注意,如果我们将结果 \u003cb\u003eR[2]\u003c/b\u003e 的值增加 1 而不是 \u003cb\u003eR[1]\u003c/b\u003e,那么值为 \u003cb\u003ei \u003d 2\u003c/b\u003e 的情况将导致逮捕,因为在这次操作后,\u003cb\u003e{R[2], R[3], R[4]}\u003c/b\u003e 将变为 \u003cb\u003e{8, 8, 8}\u003c/b\u003e,我们将有 3 个 \u003cb\u003ej\u003c/b\u003e 值从 \u003cb\u003e2\u003c/b\u003e 到 \u003cb\u003e4\u003c/b\u003e(包括),满足 \u003cb\u003eR[j] \u003d max{R[2], R[3], R[4]}\u003c/b\u003e,即,\u003cb\u003ej \u003d 2, 3, 4\u003c/b\u003e。\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003e示例 4.\u003c/b\u003e 当 \u003cb\u003eM \u003d 1\u003c/b\u003e 时,小象无法达到目标,因为对于每个 \u003cb\u003ei\u003c/b\u003e 从 \u003cb\u003e0\u003c/b\u003e 到 \u003cb\u003eN-K\u003c/b\u003e,我们至少有一个 \u003cb\u003ej\u003c/b\u003e 值,使得 \u003cb\u003eR[j] \u003d max{R[i], R[i+1], ..., R[i+K-1]}\u003c/b\u003e。\u003c/p\u003e"}}]}