Statement

Carlo, as many other people in Provincia di Treviso, produces a lot of rubbish with each activity he carries out during his day. Still, he is a strong advocate of separate waste collection, and for this reason he has N trash bins at home, indexed from 0 to N-1, each one for a different type of garbage (plastic, cans, glass, …). Every trash bin has a capacity of C_i bags, that can never be exceeded, otherwise Treviso's image would be hurt. Fortunately, every night the S.A.V.N.O. garbage truck passes by and can completely empty a single continuous interval of trash cans, removing all of their contents. Note that the garbage truck can clear at most one interval per night. Obviously, such a great service comes at a cost (the waste-tax): the price of clearing an interval is the sum of the unused capacities for each trash bin in that interval. More formally, if U_i is the number of bags in the i-th trash bin, the price of emptying an interval [L, R] is: \sum_i=L^RC_i - U_i...