{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eThe Little Elephant and his friends from the Zoo of Lviv were returning from the party. But suddenly they were stopped by the policeman Big Hippo, who wanted to make an alcohol test for elephants.\u003c/p\u003e\n\n\u003cp\u003eThere were \u003cb\u003eN\u003c/b\u003e elephants ordered from the left to the right in a row and numbered from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003eN-1\u003c/b\u003e. Let \u003cb\u003eR[i]\u003c/b\u003e to be the result of breathalyzer test of \u003cb\u003ei\u003c/b\u003e-th elephant.\u003c/p\u003e\n\n\u003cp\u003eConsidering current laws in the Zoo, elephants would be arrested if there exists \u003cb\u003eK\u003c/b\u003e consecutive elephants among them for which at least \u003cb\u003eM\u003c/b\u003e of these \u003cb\u003eK\u003c/b\u003e elephants have the maximal test result among these \u003cb\u003eK\u003c/b\u003e elephants.\u003c/p\u003e\n\n\u003cp\u003eUsing poor math notations we can alternatively define this as follows. The elephants would be arrested if there exists \u003cb\u003ei\u003c/b\u003e from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003eN-K\u003c/b\u003e, inclusive, such that for at least \u003cb\u003eM\u003c/b\u003e different values of \u003cb\u003ej\u003c/b\u003e from \u003cb\u003ei\u003c/b\u003e to \u003cb\u003ei+K-1\u003c/b\u003e, inclusive, we have \u003cb\u003eR[j] \u003d max{R[i], R[i+1], ..., R[i+K-1]}\u003c/b\u003e.\n\n\u003c/p\u003e\u003cp\u003eThe Big Hippo is very old and the Little Elephant can change some of the results. In a single operation he can add \u003cb\u003e1\u003c/b\u003e to the result of any elephant. But for each of the elephants he can apply this operation at most once.\u003c/p\u003e\n\n\u003cp\u003eWhat is the minimum number of operations that the Little Elephant needs to apply, such that the sequence of results, after all operations will be applied, let elephants to avoid the arrest? If it is impossible to avoid the arrest applying any number of operations, output \u003cb\u003e-1\u003c/b\u003e.\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e The first line of the input contains an integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows. The first line of each test case contains three space-separated integers \u003cb\u003eN, K, M\u003c/b\u003e. The second line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003e R[0], R[1], ..., R[N-1]\u003c/b\u003e denoting the test results of the elephants.\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case, output a single line containing the minimum number of operations needed to avoid the arrest.\u003c/p\u003e\n\n\u003ch3\u003eConstraints\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":"Sample 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\u003eExample case 1.\u003c/b\u003e Let\u0027s follow the poor math definition of arrest. We will consider all values of \u003cb\u003ei\u003c/b\u003e from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003eN-K \u003d 2\u003c/b\u003e, inclusive, and should count the number of values of \u003cb\u003ej\u003c/b\u003e described in the definition. If it less than \u003cb\u003eM \u003d 2\u003c/b\u003e then this value of \u003cb\u003ei\u003c/b\u003e does not cause the arrest, otherwise causes.\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\u003eFor which \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e we have \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003eConclusion\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 for \u003cb\u003ej \u003d 1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003eSo we see that initial test results of the elephants do not cause their arrest. Hence the Little Elephant does not need to apply any operations. Therefore, the answer is 0.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eExample case 2.\u003c/b\u003eWe have \u003cb\u003eN \u003d 5\u003c/b\u003e, \u003cb\u003eK \u003d 3\u003c/b\u003e, \u003cb\u003eM \u003d 3\u003c/b\u003e. Let\u0027s construct similar table as in example case 1. Here the value of \u003cb\u003ei\u003c/b\u003e will cause the arrest if we have at least \u003cb\u003e3\u003c/b\u003e values of \u003cb\u003ej\u003c/b\u003e described in the definition.\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\u003eFor which \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e we have \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003eConclusion\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 for \u003cb\u003ej \u003d 0, 1, 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003ecauses the arrest\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 for \u003cb\u003ej \u003d 1, 2, 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003ecauses the arrest\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 for \u003cb\u003ej \u003d 2, 3, 4\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003ecauses the arrest\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003eSo we see that for initial test results of the elephants each value of \u003cb\u003ei\u003c/b\u003e causes their arrest. Hence the Little Elephant needs to apply some operations in order to avoid the arrest. He could achieve his goal by adding \u003cb\u003e1\u003c/b\u003e to the result \u003cb\u003eR[2]\u003c/b\u003e. Then results will be \u003cb\u003e{R[0], R[1], R[2], R[3], R[4]} \u003d {7, 7, 8, 7, 7}\u003c/b\u003e. Let\u0027s check that now elephants will be not arrested.\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\u003eFor which \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e we have \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003eConclusion\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 for \u003cb\u003ej \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003eSo we see that now test results of the elephants do not cause their arrest. Thus we see that using 0 operations we can\u0027t avoid the arrest but using 1 operation can. Hence the answer is 1.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eExample case 3.\u003c/b\u003eWe have \u003cb\u003eN \u003d 5\u003c/b\u003e, \u003cb\u003eK \u003d 3\u003c/b\u003e, \u003cb\u003eM \u003d 3\u003c/b\u003e. Let\u0027s construct similar table as in example case 1. Here the value of \u003cb\u003ei\u003c/b\u003e will cause the arrest if we have at least \u003cb\u003e3\u003c/b\u003e values of \u003cb\u003ej\u003c/b\u003e described in the definition.\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\u003eFor which \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e we have \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003eConclusion\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 for \u003cb\u003ej \u003d 0, 1, 2\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003ecauses the arrest\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 for \u003cb\u003ej \u003d 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 3, 4\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003eSo we see that for initial test results of the elephants the value of \u003cb\u003ei \u003d 0\u003c/b\u003e causes their arrest. Hence the Little Elephant needs to apply some operations in order to avoid the arrest. He could achieve his goal by adding \u003cb\u003e1\u003c/b\u003e to the result \u003cb\u003eR[1]\u003c/b\u003e. Then results will be \u003cb\u003e{R[0], R[1], R[2], R[3], R[4]} \u003d {7, 8, 7, 8, 8}\u003c/b\u003e. Let\u0027s check that now elephants will be not arrested.\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\u003eFor which \u003cb\u003ej \u003d i, ..., i+K-1\u003c/b\u003e\u003cbr /\u003e we have \u003cb\u003eR[j] \u003d max\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003eConclusion\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 for \u003cb\u003ej \u003d 1\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 1, 3\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\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 for \u003cb\u003ej \u003d 3, 4\u003c/b\u003e\u003c/td\u003e\n\u003ctd\u003edoes not cause the arrest\u003c/td\u003e\n\u003c/tr\u003e\u003c/table\u003e\u003cp\u003eSo we see that now test results of the elephants do not cause their arrest. Thus we see that using 0 operations we can\u0027t avoid the arrest but using 1 operation can. Hence the answer is 1. Note that if we increase by 1 the result \u003cb\u003eR[2]\u003c/b\u003e instead of \u003cb\u003eR[1]\u003c/b\u003e then the value \u003cb\u003ei \u003d 2\u003c/b\u003e will cause the arrest since \u003cb\u003e{R[2], R[3], R[4]}\u003c/b\u003e will be \u003cb\u003e{8, 8, 8}\u003c/b\u003e after this operation and we will have 3 values of \u003cb\u003ej\u003c/b\u003e from \u003cb\u003e2\u003c/b\u003e to \u003cb\u003e4\u003c/b\u003e, inclusive, for which \u003cb\u003eR[j] \u003d max{R[2], R[3], R[4]}\u003c/b\u003e, namely, \u003cb\u003ej \u003d 2, 3, 4\u003c/b\u003e.\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eExample case 4.\u003c/b\u003e When \u003cb\u003eM \u003d 1\u003c/b\u003e the Little Elephant can\u0027t reach the goal since for each value of \u003cb\u003ei\u003c/b\u003e from \u003cb\u003e0\u003c/b\u003e to \u003cb\u003eN-K\u003c/b\u003e we have at least one value of \u003cb\u003ej\u003c/b\u003e for which \u003cb\u003eR[j] \u003d max{R[i], R[i+1], ..., R[i+K-1]}\u003c/b\u003e.\u003c/p\u003e\n"}}]}