{"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\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\u003e У вас есть колода из $$$n$$$ карт, и вы хотите переупорядочить ее по-новому.\u003c/p\u003e\n\u003cp\u003eУ каждой карты есть целое значение от $$$1$$$ по $$$n$$$ равное $$$p_i$$$. Все $$$p_i$$$ попарно различны. Карты в колоде пронумерованы снизу вверх, таким образом. $$$p_1$$$ лежит внизу колоды, а $$$p_n$$$ — на самом верху.\u003c/p\u003e\n\u003cp\u003e Вы перекладываете колоду шаг за шагом. На каждом шаге вы выбираете некоторое целое $$$k \u0026gt; 0$$$, берете $$$k$$$ верхних карт из вашей колоды и кладете их, не меняя порядка, на верх новой колоды. Вы применяете данную операцию, пока ваша первоначальная колода не опустеет. (Для лучшего понимания изучите примечания к тестовым примерам.)\u003c/p\u003e\n\u003cp\u003e Назовем \u003cspan class\u003d\"tex-font-style-it\"\u003e упорядоченностью колоды \u003c/span\u003e сумму $$$\\sum\\limits_{i \u003d 1}^{n}{n^{n - i} \\cdot p_i}$$$.\u003c/p\u003e\n\u003cp\u003e Для заданной колоды, определите колоду с максимально возможной упорядоченностью, которую вы можете получить, используя алгоритм, описанный выше.\n\n\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e В первой строке задано одно целое число $$$t$$$ ($$$1 \\le t \\le 1000$$$)\u0026nbsp;— количество наборов входных данных.\u003c/p\u003e\n\u003cp\u003eВ первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \\le n \\le 10^5$$$)\u0026nbsp; — количество карт в колоде.\u003c/p\u003e\n\u003cp\u003eВо второй строке заданы $$$n$$$ целых чисел $$$p_1, p_2,\\dots, p_n$$$ ($$$1 \\le p_i \\le n$$$; $$$p_i \\neq p_j$$$ if $$$i \\neq j$$$)\u0026nbsp; — значения карт в колоде в порядке снизу вверх.\u003c/p\u003e\n\u003cp\u003e Гарантируется, что сумма $$$n$$$по всем наборам входных данных не превосходит $$$10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e Для каждого набора входных данных, выведите колоду с максимально возможной упорядоченностью. Выводите значения карт начиная с нижних в колоде.\u003c/p\u003e\n\u003cp\u003eЕсли существует несколько ответов, выведите любой из них.\n\u003c/p\u003e"}},{"title":"Sample 1","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\u003e4\n4\n1 2 3 4\n5\n1 5 2 4 3\n6\n4 2 5 3 6 1\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4 3 2 1\n5 2 4 3 1\n6 1 5 3 4 2\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case, one of the optimal strategies is the next one:\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003etake $$$1$$$ card from the top of $$$p$$$ and move it to $$$p\u0027$$$: $$$p$$$ becomes $$$[1, 2, 3]$$$, $$$p\u0027$$$ becomes $$$[4]$$$;\u003c/li\u003e\n \u003cli\u003etake $$$1$$$ card from the top of $$$p$$$: $$$p$$$ becomes $$$[1, 2]$$$, $$$p\u0027$$$ becomes $$$[4, 3]$$$;\u003c/li\u003e\n \u003cli\u003etake $$$1$$$ card from the top of $$$p$$$: $$$p$$$ becomes $$$[1]$$$, $$$p\u0027$$$ becomes $$$[4, 3, 2]$$$;\u003c/li\u003e\n \u003cli\u003etake $$$1$$$ card from the top of $$$p$$$: $$$p$$$ becomes empty, $$$p\u0027$$$ becomes $$$[4, 3, 2, 1]$$$.\u003c/li\u003e\n\u003c/ol\u003e In result, $$$p\u0027$$$ has order equal to $$$4^3 \\cdot 4 + 4^2 \\cdot 3 + 4^1 \\cdot 2 + 4^0 \\cdot 1$$$ $$$\u003d$$$ $$$256 + 48 + 8 + 1 \u003d 313$$$.\n\u003cp\u003eIn the second test case, one of the optimal strategies is:\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003etake $$$4$$$ cards from the top of $$$p$$$ and move it to $$$p\u0027$$$: $$$p$$$ becomes $$$[1]$$$, $$$p\u0027$$$ becomes $$$[5, 2, 4, 3]$$$;\u003c/li\u003e\n \u003cli\u003etake $$$1$$$ card from the top of $$$p$$$ and move it to $$$p\u0027$$$: $$$p$$$ becomes empty, $$$p\u0027$$$ becomes $$$[5, 2, 4, 3, 1]$$$;\u003c/li\u003e\n\u003c/ol\u003e In result, $$$p\u0027$$$ has order equal to $$$5^4 \\cdot 5 + 5^3 \\cdot 2 + 5^2 \\cdot 4 + 5^1 \\cdot 3 + 5^0 \\cdot 1$$$ $$$\u003d$$$ $$$3125 + 250 + 100 + 15 + 1 \u003d 3491$$$.\n\u003cp\u003eIn the third test case, one of the optimal strategies is:\u003c/p\u003e\n\u003col\u003e\n \u003cli\u003etake $$$2$$$ cards from the top of $$$p$$$ and move it to $$$p\u0027$$$: $$$p$$$ becomes $$$[4, 2, 5, 3]$$$, $$$p\u0027$$$ becomes $$$[6, 1]$$$;\u003c/li\u003e\n \u003cli\u003etake $$$2$$$ cards from the top of $$$p$$$ and move it to $$$p\u0027$$$: $$$p$$$ becomes $$$[4, 2]$$$, $$$p\u0027$$$ becomes $$$[6, 1, 5, 3]$$$;\u003c/li\u003e\n \u003cli\u003etake $$$2$$$ cards from the top of $$$p$$$ and move it to $$$p\u0027$$$: $$$p$$$ becomes empty, $$$p\u0027$$$ becomes $$$[6, 1, 5, 3, 4, 2]$$$.\u003c/li\u003e\n\u003c/ol\u003e In result, $$$p\u0027$$$ has order equal to $$$6^5 \\cdot 6 + 6^4 \\cdot 1 + 6^3 \\cdot 5 + 6^2 \\cdot 3 + 6^1 \\cdot 4 + 6^0 \\cdot 2$$$ $$$\u003d$$$ $$$46656 + 1296 + 1080 + 108 + 24 + 2 \u003d 49166$$$."}}]}