{"trustable":true,"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe terrorists have planted some bombs in a building! Our hero, Little Horse, decides to rescue the people in the building. Unfortunately, there is more than one bomb, and Little Horse is unable to defuse all of them. To strive for more time for other people to escape, Little Horse decides to sacrifice himself.\u003c/p\u003e\u003cp\u003eThere are $$$n$$$ bombs in the building, each of which has a countdown clock. In the beginning, the $$$i$$$-th bomb\u0027s clock is set to $$$a_i$$$. Then:\u003c/p\u003e\u003col\u003e \u003cli\u003e Little Horse chooses one bomb, making its clock increase by $$$1$$$. \u003c/li\u003e\u003cli\u003e Every bomb\u0027s clock decreases by $$$1$$$. \u003c/li\u003e\u003cli\u003e If at least one clock becomes lower than $$$0$$$, all the bombs will explode. Otherwise, go back to step 1. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eObviously, the explosion is not avoidable. What a sad story. But Little Horse doesn\u0027t care about his survival now. He just wants to strive for more time. So can you tell him how many times he can do step 1 at most before the explosion?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains an integer $$$T$$$ ($$$1 \\le T \\le 100$$$) — the number of test cases.\u003c/p\u003e\u003cp\u003eThe first line of the input contains an integer $$$n$$$ ($$$2 \\le n \\le 10^5$$$) — the number of bombs. The sum of $$$n$$$ will not exceed $$$3\\times10^5$$$.\u003c/p\u003e\u003cp\u003eThe next line contains $$$n$$$ numbers $$$a_1,a_2,\\dots,a_n$$$ ($$$0 \\le a_1,a_2,\\dots,a_n \\le 10^9$$$) — the clocks of the bombs in the beginning.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor the $$$x$$$-th test case, if the answer is $$$y$$$, output \u003cspan class\u003d\"tex-font-style-bf\"\u003e$$$Case$$$ #$$$x$$$: $$$y$$$\u003c/span\u003e in a single line.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","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\u003e2\n2\n1 1\n3\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 3\nCase #2: 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}