{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eIt is winter now, and Max decided it\u0027s about time he watered the garden.\u003c/p\u003e\n\u003cp\u003eThe garden can be represented as \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e consecutive garden beds, numbered from \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e beds contain water taps (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th tap is located in the bed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e), which, if turned on, start delivering water to neighbouring beds. If the tap on the bed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is turned on, then after one second has passed, the bed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e will be watered; after two seconds have passed, the beds from the segment \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e - 1, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + 1]\u003c/span\u003e will be watered (if they exist); after \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e seconds have passed \u003cspan class\u003d\"tex-font-style-bf\"\u003e(\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e is an integer number)\u003c/span\u003e, the beds from the segment \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e - (\u003ci\u003ej\u003c/i\u003e - 1), \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + (\u003ci\u003ej\u003c/i\u003e - 1)]\u003c/span\u003e will be watered (if they exist). \u003cspan class\u003d\"tex-font-style-bf\"\u003eNothing changes during the seconds, so, for example, we can\u0027t say that the segment \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e - 2.5, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + 2.5]\u003c/span\u003e will be watered after \u003cspan class\u003d\"tex-span\"\u003e2.5\u003c/span\u003e seconds have passed; only the segment \u003cspan class\u003d\"tex-span\"\u003e[\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e - 2, \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e + 2]\u003c/span\u003e will be watered at that moment.\u003c/span\u003e\u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" SRC\u003d\"CDN_BASE_URL/b45cbbd14482d64c438eb5bdf225f550?v\u003d1545786645\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The garden from test \n \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. White colour denotes a garden bed without a tap, red colour — a garden bed with a tap. \n\u003c/center\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" SRC\u003d\"CDN_BASE_URL/61b75ff893375645bf5dd312b07e5c24?v\u003d1545786645\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e The garden from test \n \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e after \n \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e seconds have passed after turning on the tap. White colour denotes an unwatered garden bed, blue colour — a watered bed. \n\u003c/center\u003e\n\u003cp\u003eMax wants to \u003cspan class\u003d\"tex-font-style-bf\"\u003eturn on all the water taps at the same moment\u003c/span\u003e, and now he wonders, what is the minimum number of seconds that have to pass after he turns on some taps until the whole garden is watered. Help him to find the answer!\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains one integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e — the number of test cases to solve (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e ≤ 200\u003c/span\u003e).\u003c/p\u003e\n\u003cp\u003eThen \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e test cases follow. The first line of each test case contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 200\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ek\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — the number of garden beds and water taps, respectively.\u003c/p\u003e\n\u003cp\u003eNext line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — the location of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th water tap. It is guaranteed that for each \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" SRC\u003d\"CDN_BASE_URL/79990d32d1994b06f6908a89c0f3a3b1?v\u003d1545786645\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e condition \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e - 1\u003c/sub\u003e \u0026lt; \u003ci\u003ex\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e holds.\u003c/p\u003e\n\u003cp\u003eIt is guaranteed that the sum of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e over all test cases doesn\u0027t exceed \u003cspan class\u003d\"tex-span\"\u003e200\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eNote that in hacks you have to set \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d 1\u003c/span\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case print one integer — the minimum number of seconds that have to pass after Max turns on some of the water taps, until the whole garden is watered.\u003c/p\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e5 1\u003cbr\u003e3\u003cbr\u003e3 3\u003cbr\u003e1 2 3\u003cbr\u003e4 1\u003cbr\u003e1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e1\u003cbr\u003e4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e给你编号1~n的花园,花园从左到右排成一排。其中有k个花园有水龙头,当水龙头所在的花园浇满后,会流向左右相邻花园,现在同时打开所有水龙头,问你多长时间后n个花园能被浇满The first example consists of \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e tests:\u003c/p\u003e\n\u003col\u003e \n \u003cli\u003e There are \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e garden beds, and a water tap in the bed \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e. If we turn it on, then after \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e second passes, only bed \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e will be watered; after \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e seconds pass, beds \u003cspan class\u003d\"tex-span\"\u003e[1, 3]\u003c/span\u003e will be watered, and after \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e seconds pass, everything will be watered. \u003c/li\u003e\n \u003cli\u003e There are \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e garden beds, and there is a water tap in each one. If we turn all of them on, then everything will be watered after \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e second passes. \u003c/li\u003e\n \u003cli\u003e There are \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e garden beds, and only one tap in the bed \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. It will take \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e seconds to water, for example, bed \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e. \u003c/li\u003e\n\u003c/ol\u003e"}}]}