```5
1 5 2 4 3```

## 样例输出

`55 35 23 15 5`

## 思路

（当然，听说找一个点左边值递减的点和左边值递增的点好像还可以用很多其他方法，具体有什么忘了，但是我觉得用单调栈会相对简单很多吧。。。）
（上面括号最后一句仅表个人观点，勿喷谢谢）

## 比赛时

（结果到最后还是没想到第三题处理完的数是一一对应的QAQ）

## 代码

```#include<cstdio>
#include<iostream>

using namespace std;

struct node {
int x, num;
}bigstack[101], smallstack[101];
int n, a[100001], ans[100001], bigtop, smalltop, maxn, minn;
int lft, bignow, smallnow;

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

for (int i = 1; i <= n; i++) {
while (bigtop && bigstack[bigtop].x <= a[i]) bigtop--;
while (smalltop && smallstack[smalltop].x >= a[i]) smalltop--;//栈的弹出

bigstack[++bigtop] = (node){a[i], i};//插入
smallstack[++smalltop] = (node){a[i], i};
maxn = minn = a[i];
lft = i;
bignow = bigtop - 1;
smallnow = smalltop - 1;

while (bignow || smallnow) {//一点一点往后移，算贡献
if (bignow && smallnow) {
if (bigstack[bignow].num >= smallstack[smallnow].num) {
ans[i - lft + 1] += maxn * minn;
ans[i - bigstack[bignow].num + 1] -= maxn * minn;
lft = bigstack[bignow].num;
maxn = bigstack[bignow].x;
bignow--;
}
else {
ans[i - lft + 1] += maxn * minn;
ans[i - smallstack[smallnow].num + 1] -= maxn * minn;
lft = smallstack[smallnow].num;
minn = smallstack[smallnow].x;
smallnow--;
}

continue;
}

if (bignow) {
ans[i - lft + 1] += maxn * minn;
ans[i - bigstack[bignow].num + 1] -= maxn * minn;
lft = bigstack[bignow].num;
maxn = bigstack[bignow].x;
bignow--;
}

else {
ans[i - lft + 1] += maxn * minn;
ans[i - smallstack[smallnow].num + 1] -= maxn * minn;
lft = smallstack[smallnow].num;
minn = smallstack[smallnow].x;
smallnow--;
}
}

ans[i - lft + 1] += maxn * minn;
ans[i + 1] -= maxn * minn;
}

for (int i = 1; i <= n; i++) {
ans[i] += ans[i - 1];//因为是差分，所以要加上前面的
printf("%d ", ans[i]);
}

return 0;
}```