Wonderful Jump

题意翻译

### 题目描述 给定整数 $n$ 和长度为 $n$ 的序列 $a$。 从位置 $i$ 跳到位置 $j(1\leq i\leq j\leq n)$ 需要花费 $\min(a_i,a_{i+1},\cdots,a_j)\times(j-i)^2$ 枚金币。 对于 $k=1,2,\cdots,n$，求出从位置 $1$ 经若干次跳跃后跳到位置 $k$ 需要的最小金币总数。 ### 输入格式 第一行输入一个整数 $n(2\leq n\leq4\times10^5)$。 接下来输入一行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\leq a_i\leq n)$。 ### 输出格式 输出一行 $n$ 个整数，其中第 $k$ 个整数表示从位置 $1$ 到位置 $k$ 所需的最小金币数。

题目描述

You are given an array of positive integers $ a_1,a_2,\ldots,a_n $ of length $ n $ . In one operation you can jump from index $ i $ to index $ j $ ( $ 1 \le i \le j \le n $ ) by paying $ \min(a_i, a_{i + 1}, \ldots, a_j) \cdot (j - i)^2 $ eris. For all $ k $ from $ 1 $ to $ n $ , find the minimum number of eris needed to get from index $ 1 $ to index $ k $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 2 \le n \le 4 \cdot 10^5 $ ). The second line contains $ n $ integers $ a_1,a_2,\ldots a_n $ ( $ 1 \le a_i \le n $ ).

输出格式

Output $ n $ integers — the $ k $ -th integer is the minimum number of eris needed to reach index $ k $ if you start from index $ 1 $ .

输入输出样例

输入样例 #1

3
2 1 3

输出样例 #1

0 1 2

输入样例 #2

6
1 4 1 6 3 2

输出样例 #2

0 1 2 3 6 8

输入样例 #3

2
1 2

输出样例 #3

0 1

输入样例 #4

4
1 4 4 4

输出样例 #4

0 1 4 8

说明

In the first example: - From $ 1 $ to $ 1 $ : the cost is $ 0 $ , - From $ 1 $ to $ 2 $ : $ 1 \rightarrow 2 $ — the cost is $ \min(2, 1) \cdot (2 - 1) ^ 2=1 $ , - From $ 1 $ to $ 3 $ : $ 1 \rightarrow 2 \rightarrow 3 $ — the cost is $ \min(2, 1) \cdot (2 - 1) ^ 2 + \min(1, 3) \cdot (3 - 2) ^ 2 = 1 + 1 = 2 $ . In the fourth example from $ 1 $ to $ 4 $ : $ 1 \rightarrow 3 \rightarrow 4 $ — the cost is $ \min(1, 4, 4) \cdot (3 - 1) ^ 2 + \min(4, 4) \cdot (4 - 3) ^ 2 = 4 + 4 = 8 $ .

**题目大意：**

给定一个长度为 $ n $ 的正整数数组 $ a_1, a_2, \ldots, a_n $。

你可以从索引 $ i $ 跳到索引 $ j (1 \le i \le j \le n) $，跳跃的花费是 $ \min(a_i, a_{i+1}, \ldots, a_j) \times (j - i)^2 $ 枚金币。

对于 $ k = 1, 2, \ldots, n $，计算从索引 $ 1 $ 开始，通过若干次跳跃到达索引 $ k $ 所需的最少金币数。

**输入格式：**

第一行包含一个整数 $ n (2 \le n \le 4 \times 10^5) $。

第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n (1 \le a_i \le n) $。

**输出格式：**

输出 $ n $ 个整数，第 $ k $ 个整数表示从索引 $ 1 $ 到索引 $ k $ 所需的最少金币数。

**输入输出样例：**

**输入样例 #1：**
```
3
2 1 3
```
**输出样例 #1：**
```
0 1 2
```

**输入样例 #2：**
```
6
1 4 1 6 3 2
```
**输出样例 #2：**
```
0 1 2 3 6 8
```

**输入样例 #3：**
```
2
1 2
```
**输出样例 #3：**
```
0 1
```

**输入样例 #4：**
```
4
1 4 4 4
```
**输出样例 #4：**
```
0 1 4 8
```

**说明：**

在第一个例子中：

- 从 $ 1 $ 到 $ 1 $：花费是 $ 0 $，
- 从 $ 1 $ 到 $ 2 $：$ 1 \rightarrow 2 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 = 1 $，
- 从 $ 1 $ 到 $ 3 $：$ 1 \rightarrow 2 \rightarrow 3 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 + \min(1, 3) \times (3 - 2)^2 = 1 + 1 = 2 $。

在第四个例子中，从 $ 1 $ 到 $ 4 $：$ 1 \rightarrow 3 \rightarrow 4 $ — 花费是 $ \min(1, 4, 4) \times (3 - 1)^2 + \min(4, 4) \times (4 - 3)^2 = 4 + 4 = 8 $。**题目大意：** 给定一个长度为 $ n $ 的正整数数组 $ a_1, a_2, \ldots, a_n $。 你可以从索引 $ i $ 跳到索引 $ j (1 \le i \le j \le n) $，跳跃的花费是 $ \min(a_i, a_{i+1}, \ldots, a_j) \times (j - i)^2 $ 枚金币。 对于 $ k = 1, 2, \ldots, n $，计算从索引 $ 1 $ 开始，通过若干次跳跃到达索引 $ k $ 所需的最少金币数。 **输入格式：** 第一行包含一个整数 $ n (2 \le n \le 4 \times 10^5) $。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n (1 \le a_i \le n) $。 **输出格式：** 输出 $ n $ 个整数，第 $ k $ 个整数表示从索引 $ 1 $ 到索引 $ k $ 所需的最少金币数。 **输入输出样例：** **输入样例 #1：** ``` 3 2 1 3 ``` **输出样例 #1：** ``` 0 1 2 ``` **输入样例 #2：** ``` 6 1 4 1 6 3 2 ``` **输出样例 #2：** ``` 0 1 2 3 6 8 ``` **输入样例 #3：** ``` 2 1 2 ``` **输出样例 #3：** ``` 0 1 ``` **输入样例 #4：** ``` 4 1 4 4 4 ``` **输出样例 #4：** ``` 0 1 4 8 ``` **说明：** 在第一个例子中： - 从 $ 1 $ 到 $ 1 $：花费是 $ 0 $， - 从 $ 1 $ 到 $ 2 $：$ 1 \rightarrow 2 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 = 1 $， - 从 $ 1 $ 到 $ 3 $：$ 1 \rightarrow 2 \rightarrow 3 $ — 花费是 $ \min(2, 1) \times (2 - 1)^2 + \min(1, 3) \times (3 - 2)^2 = 1 + 1 = 2 $。 在第四个例子中，从 $ 1 $ 到 $ 4 $：$ 1 \rightarrow 3 \rightarrow 4 $ — 花费是 $ \min(1, 4, 4) \times (3 - 1)^2 + \min(4, 4) \times (4 - 3)^2 = 4 + 4 = 8 $。