{"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\u003eOn December 4th, ICPC2021 Nanjing was held. During the contest, Walk_alone (abbr. WA) did nothing but be stuck by Problem D, which was an easy data structure problem with a background of an adapted bubble sort. So he has being scolded by his teammates for a long time for losing a gold medal.\u003c/p\u003e\u003cp\u003eToday, his teammates gave him another adjusted sorting algorithm to help him overcome his psychological shadow. But his dread and fear stops him from even thinking about this problem. Help him solve the problem below to avoid being scolded by his teammates again! \u003c/p\u003e\u003cp\u003eIts pseudo-code is shown below.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/bcf3ce5934365c16dfb528d9b848401e?v\u003d1719110269\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eObviously not every sequence can be sorted by this algorithm, but it does not matter, and here comes the question: \u003c/p\u003e\u003cp\u003eGiven a \u003cspan class\u003d\"tex-font-style-bf\"\u003epermutation\u003c/span\u003e $$$A\u003d\\{a_1,a_2,\\cdots, a_n\\}$$$. Let $$$A_k\u003d\\{a_1,a_2,\\cdots, a_k\\}$$$. Your task is to count the total number of times $$$m$$$ is assigned if we call $$${\\rm SORT}(A_k)$$$ for every $$$k \\ (1 \\le k \\le n)$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer $$$n\\ (1\\le n\\le 10^6)$$$ indicating the length of the sequence.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers $$$a_1,a_2,\\cdots, a_n\\ (1\\le a_i\\le n)$$$ indicating the given permutation.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one line containing $$$n$$$ integers $$$s_1,s_2,\\cdots, s_n$$$ separated by a space, where $$$s_i$$$ indicates the total number of times $$$m$$$ is assigned if we call $$${\\rm SORT}(A_i)$$$.\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\u003e6\n5 4 2 6 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 4 8 11 13 19 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e6\n4 5 2 3 6 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3 6 8 13 17 \u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}