{"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\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":"\u003cp\u003eJoão has just bought a new game from the store: \u003cspan class\u003d\"tex-font-style-it\"\u003eLampião, o Rei do Cangaço\u003c/span\u003e. The main character of the game is Lampião, a known figure of Soteropolitan culture and probably the most famous \u003cspan class\u003d\"tex-font-style-it\"\u003ecangaceiro\u003c/span\u003e of all time. There is a lot of controversy around the reputation of the \u003cspan class\u003d\"tex-font-style-it\"\u003ecangaceiros\u003c/span\u003e, but João definitely must stick to their cause to beat this game.\u003c/p\u003e\u003cp\u003eIn this game, João must control Lampião through a series of mini-games. There is one mini-game that caught João\u0027s attention: the \u003cspan class\u003d\"tex-font-style-it\"\u003etreasure hunt\u003c/span\u003e. In this mini-game, there are $$$n$$$ houses in a row, numbered 1 to $$$n$$$ from left to right. Lampião is supposed to break into some of these houses. After breaking into a house, Lampião may \u003cspan class\u003d\"tex-font-style-bf\"\u003eearn\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-bf\"\u003elose\u003c/span\u003e coins (some houses are guarded by \u003cspan class\u003d\"tex-font-style-it\"\u003ejagunços\u003c/span\u003e, which are dangerous mercenaries crazy for money). More specifically, let $$$C$$$ be how many coins Lampião possesses before breaking into the $$$i$$$-th house. Lampião will have $$$C + a_i$$$ coins after breaking into it, where $$$a_i$$$ may actually be negative.\u003c/p\u003e\u003cp\u003eLampião is initially standing in front of one of the houses. Also, he initially possesses $$$10^9$$$ coins. The game is played in turns. The turns are numbered starting from one. In the $$$i$$$-th turn, one of the two actions below can be taken:\u003c/p\u003e\u003col\u003e \u003cli\u003e Move Lampião $$$3i$$$ houses to the right while breaking into \u003cspan class\u003d\"tex-font-style-bf\"\u003eevery\u003c/span\u003e one of them, \u003cspan class\u003d\"tex-font-style-bf\"\u003eexcept\u003c/span\u003e for the final one. For instance, if this is the first turn, there are 4 houses, Lampião is standing by house 1 and this action is taken, Lampião will move to house 4 while breaking into houses 1, 2 and 3; \u003c/li\u003e\u003cli\u003e Just move Lampião $$$3i$$$ houses to the right. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eThe game instantly ends when Lampião goes beyond the $$$n$$$-th house. \u003c/p\u003e\u003cp\u003eYour task is to compute, for every possible starting position, the maximum profit Lampião can achieve if João acts optimally. The profit is defined as the difference between the final amount of coins and the initial amount of coins. Notice that the optimal profit is never negative, since João can choose not to take action (1).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains an integer $$$n$$$ ($$$1 \\leq n \\leq 50000$$$) – the number of houses in the mini-game.\u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ space-separated integers. The $$$i$$$-th of them is $$$a_i$$$ ($$$-300 \\leq a_i \\leq 300$$$).\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$n$$$ lines. The $$$i$$$-th of them should contain a single integer – the maximum possible profit if Lampião starts from the $$$i$$$-th house.\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\u003e5\n1 2 3 4 -5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n9\n2\n0\n0\n\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\u003e7\n-3 -5 -7 -9 9 -2 -4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n3\n0\n0\n3\n0\n0\n\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\u003e9\n1 2 3 4 5 6 5 -7 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e21\n20\n18\n15\n16\n6\n0\n0\n2\n\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\u003e4\n1 -1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n4\n5\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}