{"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":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eYou are given an array consisting of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\n\u003cp\u003eYou are ready to delete elements in the array in order. The order elements of the array are deleted is defined as a permutation of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e.\n\u003cp\u003eAfter each element is destroyed you should find out the sum of the segment of the array, such that it contains no destroyed elements and the sum of its elements is maximum. "}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100 000\u003c/span\u003e)\u0026nbsp;— the length of the array.\u003c/p\u003e\n\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e). \u003c/p\u003e\n\u003cp\u003eThe third line contains a permutation — the order used to destroy elements.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line should contain a single integer\u0026nbsp;— the maximum sum of elements , after first \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e operations are performed.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4\u003cbr\u003e1 3 2 5\u003cbr\u003e3 4 1 2\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e5\u003cbr\u003e4\u003cbr\u003e3\u003cbr\u003e0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003col\u003e \n \u003cli\u003e Third element is deleted. Array is now \u003cspan class\u003d\"tex-span\"\u003e1\u0026nbsp;3\u0026nbsp; * \u0026nbsp;5\u003c/span\u003e. Segment with maximum sum \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e consists of one integer \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e. \u003c/li\u003e\n \u003cli\u003e Fourth element is deleted. Array is now \u003cspan class\u003d\"tex-span\"\u003e1\u0026nbsp;3\u0026nbsp; * \u0026nbsp; * \u003c/span\u003e. Segment with maximum sum \u003cspan class\u003d\"tex-span\"\u003e4\u003c/span\u003e consists of two integers \u003cspan class\u003d\"tex-span\"\u003e1\u0026nbsp;3\u003c/span\u003e. \u003c/li\u003e\n \u003cli\u003e First element is deleted. Array is now \u003cspan class\u003d\"tex-span\"\u003e * \u0026nbsp;3\u0026nbsp; * \u0026nbsp; * \u003c/span\u003e. Segment with maximum sum \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e consists of one integer \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e. \u003c/li\u003e\n \u003cli\u003e Last element is deleted. The answer is equal to \u003cspan class\u003d\"tex-span\"\u003e0\u003c/span\u003e. \u003c/li\u003e\n\u003c/ol\u003e"}}]}