D-牛牛的滑动窗口_2020牛客NOIP赛前集训营-普及组（第一场）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛牛最近学习了滑动窗口类的算法，滑动窗口算法可以解决一些线性数组的离线静态区间查询类问题。

具体来说，假设对于一个数组进行m次静态区间查询问题。如果这些查询满足条件： $\forall i,j$ 当 $l_i \leq l_j$ 时，总有 $r_i \leq r_j$ 。（i,j表示查询的编号，l,r表示查询的左右端点）

接下来只要查询的问题满足可以快速插入和删除单点，就可以使用滑动窗口优化，将这m次查询的复杂度降低到O(n)。

显然，如果对于一个数组的区间查询问题，查询的区间长度给定为k时，总是满足 $\forall i,j$ 当 $l_i \leq l_j$ 时，总有 $r_i \leq r_j$ 这一条件的。

牛牛接下来想要问你的问题也和定长滑动窗口有关。

众所周知，长度为k的滑动窗口从左到右去截取一个长度大小为n的数组时，一共可以截取到n-k+1个子数组。

牛牛将这n-k+1个子数组的极大值与极小值的乘积求和称为该数组的"第k窗口值"。

举个例子，假设长度为5的数组为[1,5,2,4,3]，长度为3的滑动窗口可以截取三个子数组，它们分别为[1,5,2],[5,2,4],[2,4,3]。

所以该数组的“第3窗口值”为1*5+2*5+2*4=23。

对于一个给定大小的数组n，牛牛现在想要知道它的第1,2,3,4,5...n窗口值各是多少，请你编写程序解决他的问题。

第一行输入一个正整数n，表示数组的大小。

接下来一行输入n个正整数，表示数组的内容

输出一行n个正整数，表示滑动窗口的长度分别为1,2,3,4,5...n 时，问题的答案。

输出的整数之间用空格隔开，行末不允许有多余空格。

示例1

复制

5
1 5 2 4 3

复制

55 35 23 15 5

第1窗口值=1*1+5*5+2*2+4*4+3*3=55
第2窗口值=5*1+5*2+4*2+4*3=35
第3窗口值=5*1+5*2+4*2=23
第4窗口值=5*1+5*2=15
第5窗口值=5*1=5

对于的测试数据，保证
对于的测试数据，保证
对于的测试数据，保证
对于的测试数据，保证
对于另外的测试数据，保证
对于的测试数据，保证