美食的要素是料理、时机、同伴。以及……

朱莉

各位安好，我是晴奈。距离新年时发生的那些事，已经过去一周了呢。

简单回顾一下上周的经历，这场新年风波讲的是：为了保护濒临倒闭的小餐馆“麻雀亭”，美食研究会仅凭对美食的执着，便与大型流通企业“喵食品”展开了较量。喵食品试图收购麻雀亭并将其改为连锁店，于是我们接受了以餐馆命运为赌注的料理对决。过程中，连美食头盔团也被卷了进来，城市的一角闹得天翻地覆。最终，经过一场较量，麻雀亭保住了原来的模样，得以继续经营。而今天，我们也有了一个美好的新目标：寻找更多这样的宝藏餐馆，让世人知晓。

我们美食研究会精挑细选了共 $N$ 家餐馆，并记录了第 $i$ 家餐馆的美味值为 $A_i$。我们打算策划一趟按顺序从第 $1$ 家走到第 $N$ 家的巡游。如果有不合心意的餐馆……就提前炸掉好了。我们可以从这 $N$ 家餐馆中挑选若干家炸掉，再将后面的餐馆按原顺序向前补齐，依次拜访。啊，巡游途中不吃东西可不行，所以至少要留下两家餐馆呢。 按顺序拜访剩余餐馆时，我们要看看美味是否在不断提升。

对了，有些餐馆可能由风纪委员会守卫……不过，幸好我们已经掌握了这些情报。如果 $S_i=\texttt{0}$，就可以炸掉第 $i$ 家餐馆。但如果 $S_i=\texttt{1}$，很遗憾，就不能炸掉它了。毕竟，我们可不想毁了这趟特别的美食巡游。呵呵呵。

将连续拜访的两家餐馆视为一对，如果下一家的食物比上一家更美味，我们的心情就会提升，两者的美味值之差就是提升量。反过来，如果下一家更差，心情便会下降相应的数值。把按顺序拜访所有剩余餐馆时，相邻两家之间的美味值差分全部相加，得到的值就称作满意度吧？真想知道我们能获得的最大满意度呢。不过，我们还是想尽可能品尝更多不同的美味，所以在满意度达到最大值的巡游中，希望炸掉的餐馆数量尽可能少。

严格定义满意度的话……设炸掉部分餐馆后剩下 $M$ 家，第 $i$ 家的美味值为 $B_i$。那么满意度就是

了。

来吧，老师。让我们求出满意度的最大值，以及为此至少需要炸掉多少家餐馆。

所有测试用例的 $N$ 之和不超过 $200\,000$。

时间限制

1000 ms

内存限制

1024 MB

检查器

CUSTOM