https://www.luogu.com.cn/problem/P2422

kkk 做了一个人体感觉分析器。每一天，人都有一个感受值 A_iAi​，A_iAi​ 越大，表示人感觉越舒适。在一段时间 \left[i, j\right][i,j] 内，人的舒适程度定义为 \left[i, j\right][i,j] 中最不舒服的那一天的感受值 \times× \left[i, j\right][i,j]中每一天感受值的和。现在给出 kkk 在连续 NN 天中的感受值，请问，在哪一段时间，kkk 感觉最舒适？

第一行为 NN，代表数据记录的天数。

第二行 NN 个整数，代表每一天的感受值。

一行，表示在最舒适的一段时间中的感受值。

输入 #1复制

输出 #1复制

kkk 最开心的一段时间是第 33 天到第 55 天，开心值：(6+4+5)\times4=60(6+4+5)×4=60。

对于 30\%30% 的数据，1\le N\le 1001≤N≤100。

对于 70\%70% 的数据，1\le N\le 20001≤N≤2000。

对于 100\%100% 的数据，1\le N\le 1000001≤N≤100000，1\le \texttt{感受值}\le 10000001≤感受值≤1000000。

最开始自己的想法是先ST表预处理，然而发现这个l,r是不固定的，这样去做O(n^2)的。然后看到有些大佬 单次枚举求解（二分+区间最小检验） emm当然神仙们的过题办法很多。

这里的想法是转化一下枚举的思路，最小值只有n个，那我们判最小值为n时，以这个n为中心向两边拓展，找到小于n的位置，两边同时找到这样的区间就是最大的和区间。暴力的话选择一个i,再O（n）去扫一遍。O(n^2)

再进行优化就是O（n）单调栈预处理出每个点的左右极限区间

用单调栈求出左边第一个比当前元素i小的元素记作Li​，右边为Ri​，于是我们可以再求一遍前缀和，最后这个元素对应的答案就是：(sum[R[i]-1]-sum[L[i]]) * a[i]

对单调栈的模拟：

样例：3 1 6 4 5 2

{3}

R[1]=2;(以后R[X]=I中X和I都是下标)

{1}

{1,6}

R[3]=4;

{1,4}

{1,4,5}

R[5]=6;

{1,4}

R[4]=6;

{1}

{1,2}

然后发现还有两个点的最右端区间点没有找到，说明这时候栈里面的元素的最右端的节点是n+1;

左端同理；