已知一长度为 n 的序列 a。

定义一长度为 n 的序列 x 是合法的当且仅当其所有前缀的和都小于等于其前缀的长度，且其所有后缀的和都小于等于后缀的长度。定义其权值为其与 a 每一位相乘得到的结果的和。

求权值最大的合法序列 x 的权值。

n 小于等于十万，要求不能通过求解对偶问题的方式求解此题。

人在外面，打 latex 太麻烦了，见谅