{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"FJ has purchased N (1 \u0026lt;\u003d N \u0026lt;\u003d 2000) yummy treats for the cows who get money for giving vast amounts of milk. FJ sells one treat per day and wants to maximize the money he receives over a given period time.\r\u003cbr\u003e\r\u003cbr\u003eThe treats are interesting for many reasons:\u003cul\u003e\u003cli\u003eThe treats are numbered 1..N and stored sequentially in single file in a long box that is open at both ends. On any day, FJ can retrieve one treat from either end of his stash of treats.\u003c/li\u003e\u003cli\u003eLike fine wines and delicious cheeses, the treats improve with age and command greater prices.\u003c/li\u003e\u003cli\u003eThe treats are not uniform: some are better and have higher intrinsic value. Treat i has value v(i) (1 \u0026lt;\u003d v(i) \u0026lt;\u003d 1000).\u003c/li\u003e\u003cli\u003eCows pay more for treats that have aged longer: a cow will pay v(i)*a for a treat of age a.\u003c/li\u003e\u003c/ul\u003eGiven the values v(i) of each of the treats lined up in order of the index i in their box, what is the greatest value FJ can receive for them if he orders their sale optimally?\r\u003cbr\u003e\r\u003cbr\u003eThe first treat is sold on day 1 and has age a\u003d1. Each subsequent day increases the age by 1."}},{"title":"Input","value":{"format":"HTML","content":"Line 1: A single integer, N\r\u003cbr\u003e\r\u003cbr\u003eLines 2..N+1: Line i+1 contains the value of treat v(i)"}},{"title":"Output","value":{"format":"HTML","content":"Line 1: The maximum revenue FJ can achieve by selling the treats"}},{"title":"Sample","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\r\n1\r\n3\r\n1\r\n5\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e43\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Explanation of the sample:\r\u003cbr\u003e\r\u003cbr\u003eFive treats. On the first day FJ can sell either treat #1 (value 1) or treat #5 (value 2).\r\u003cbr\u003e\r\u003cbr\u003eFJ sells the treats (values 1, 3, 1, 5, 2) in the following order of indices: 1, 5, 2, 3, 4, making 1x1 + 2x2 + 3x3 + 4x1 + 5x5 \u003d 43."}}]}