{"trustable":true,"sections":[{"title":"Background","value":{"format":"MD","content":"NOIP2015 Day2T1"}},{"title":"Description","value":{"format":"MD","content":"The annual \"Stone Skipping\" competition is about to begin!\n\nThe competition will take place in a straight river with some giant rocks scattered along it. The organizing committee has selected two rocks as the starting point and the endpoint of the competition. Between the starting point and the endpoint, there are $N$ rocks (excluding the rocks at the starting point and endpoint). During the competition, participants will start from the starting point and jump to adjacent rocks in each step until they reach the endpoint.\n\nTo increase the difficulty of the competition, the organizing committee plans to remove some rocks to maximize the shortest jumping distance for the participants. Due to budget constraints, the committee can remove a maximum of $M$ rocks between the starting point and the endpoint (excluding the rocks at the starting point and endpoint)."}},{"title":"Input","value":{"format":"MD","content":"The first line contains three integers $L,N,M$, representing the distance from the starting point to the endpoint, the number of rocks between the starting point and the endpoint, and the maximum number of rocks the committee can remove. It is guaranteed that $L \\geq 1$ and $N \\geq M \\geq 0$.\n\nThe next $N$ lines each contain an integer. The integer on the $i$th line, $D_i\\,( 0 \u003c D_i \u003c L)$, represents the distance between the $i$th rock and the starting point. These rocks are given in order of increasing distance from the starting point and no two rocks are at the same position."}},{"title":"Output","value":{"format":"MD","content":"An integer, the maximum value of the shortest jumping distance."}},{"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\u003e25 5 2 \n2\n11\n14\n17 \n21\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"### Explanation for Sample 1\n\nBy removing the two rocks at distances $2$ and $14$ from the starting point, the shortest jumping distance is $4$ (jumping from the rock at distance $17$ to the rock at distance $21$, or jumping from the rock at distance $21$ to the endpoint).\n\n### Constraints\n\nFor $20\\%$ data, $0 \\le M \\le N \\le 10$.\nFor $50\\%$ data, $0 \\le M \\le N \\le 100$.\nFor $100\\%$ data, $0 \\le M \\le N \\le 50000,1 \\le L \\le 10^9$."}}]}