{"trustable":false,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cdiv\u003e\n 上回书说道不愿透露姓名的巨巨还剩下一个数组,这个数组记录了他学习c++ \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e语言的过程。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n \u003c/div\u003e \n \u003cdiv\u003e\n 现在这个数组a里有一些字符,第i个字符的数量是a[i]。巨巨想用这些字符来构造一些回文串好让他的程序通过编译。\n \u003c/div\u003e \n \u003cdiv\u003e\n 他想知道各种组合方案中最短字符串长度的最大值。\n \u003c/div\u003e \n \u003cdiv\u003e\n \u0026nbsp;\n \u003c/div\u003e \n \u003cdiv\u003e \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e举个栗子:\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n \u003c/div\u003e \n \u003cdiv\u003e\n 现在有 ‘a’, ‘b’, ‘c’, ‘d’ \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e四种字符并且他们的数量是\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e {2,3,2,2} \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e巨巨可以构造出\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e { \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“acdbbbdca”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e}, { \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“abbba”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e, \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“cddc”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e}, { \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“aca”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e, \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“bbb”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e, \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“dcd”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e},或{ \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e“acdbdca”\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e, “bb”} \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e四种方案\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e.\n \u003c/div\u003e \n \u003cdiv\u003e\n 在以上方案中,第一个方案的最短字符串长度比其他三种方案中的最短字符串长度都长,为9。\n \u003c/div\u003e \n \u003cdiv\u003e\n \u0026nbsp;\n \u003c/div\u003e \n \u003cdiv\u003e \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e回文串嘛,大家都懂的就不废话了。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n \u003c/div\u003e \n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv\u003e\n 多组测试数据。第一行一个整形t,代表测试数据的组数。\n\u003c/div\u003e \n\u003cdiv\u003e\n 对于每组测试数据,第一行一个整形n(1\u0026lt;\u003dn\u0026lt;\u003d \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e105),代表字符的种类数。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e接下来一行n个数,a1\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e, \n \u003cspan\u003e\u003cspan\u003e\u003cspan\u003ea2\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e,...,an(0\u0026lt;\u003dai\u0026lt;\u003d104);\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e对于每组测试数据,输出一个代表答案的整数。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e·\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e\r\n4\r\n4\r\n1 1 2 4\r\n3\r\n2 2 2\r\n5\r\n1 1 1 1 1\r\n5\r\n1 1 2 2 3\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e\r\n3\r\n6\r\n1\r\n3\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cp\u003e 真·签到题\u003c/p\u003e"}}]}