Description：

给出一个序列，每个位置有权值 $a_i$ ，开始你在第 $s$ 个位置。现在你一共可以行动 $t$ 秒，每秒可以移动到两侧的位置，或取走当前位置的权值，每个位置的权只能被取走一次，位置可以被多次访问，最大化取得的权值和。

$1\leqslant n\leqslant 10^5$

Solution：

首先很容易看出最后一定是先向左走一段，然后再向右走一段，设 $fl[x]$ 表示先向左再折返走 $x$ 秒的最优解， $pl[x]$ 是位置， $fr[y],pr[y]$ 同理， $gl[x],ql[x]$ 是只向左走，但是最后回到原点， $gr[y],qr[y]$ 同理，那么我们的答案就是： $$ ans=\max_{i=1}^n(\max(gl[x]+fr[y],gr[y]+fl[x])) $$ 四个的求法都类似，现在只考虑求 $fl[x]$ ，有一个很重要的单调性是 $pl[x+1]\leqslant pl[x]$ ，这个如果用反证法比较容易理解，那么我们就可以用一个类似分治优化决策单调性 $DP$ 的方式：设 $solve(l,r)$ 表示当前要解决的左端点在 $[l,r]$ ，