MAXI - Get higher and higher

## 题目描述 有一个长度为 $n$ 的序列，有 $n$ 次询问： 第 $1$ 次询问，每 $1$ 个连续的数内取最大值，求总和。 第 $2$ 次询问，每 $2$ 个连续的数内取最大值，求总和。 ··· 第 $n$ 次询问，每 $n$ 个连续的数内取最大值，求总和。 ## 输入格式 一行一个整数 $n$ ，接下来 $n$ 个整数，描述了整个序列。 ## 输出格式 $n$ 行，表示每一次询问的结果。 ## 输入输出样例 输入： ``` 5 5 3 4 2 3 ``` 输出： ``` 17 16 13 9 5 ``` ## 样例解释 对于第 $1$ 次询问，每一段连续的数为$(5) , (3) , (4) , (2) , (3)$ 。其最大值和为 $17 = 5+3+4+2+3$ 。 对于第 $2$ 次询问，每一段连续的数为$(5,3) , (3,4) , (4,2) , (2,3)$ 。其最大值为 $16 = 5+4+4+3$ 。 之后同理。 ## 数据范围 $n \le 5 \times 10^{5}$ @Licykoc

You are travelling to Kullu Manili, a hill station in India. You saw some huge mountains and very curious to climb the highest ones. Assume that there are **n** mountains of height **hi** given. But you were wondering about what could be the total height i need to climb if I climb only the mountain of maximum height only in a segment of k continuous mountains, considering all k segements possible. You want to calculate this for all k, such that 1<=k<=n. Mathematically, we need to find the sum of maximum element in each possible continuous segment of size k.

The first line contains an input **n**. Then **n** numbers follow, denoting the height of **ith** mountain.

Output **n** lines, where ith line contains the sum of height of mountains to climb considering all continuous segments of size **i**.

5
5 3 4 2 3

17