CF1499C.Minimum Grid Path

Let's say you are standing on the $XY$-plane at point $(0, 0)$ and you want to reach point $(n, n)$.

You can move only in two directions:

• to the right, i. e. horizontally and in the direction that increase your $x$ coordinate,
• or up, i. e. vertically and in the direction that increase your $y$ coordinate.

In other words, your path will have the following structure:

• initially, you choose to go to the right or up;
• then you go some positive integer distance in the chosen direction (distances can be chosen independently);
• after that you change your direction (from right to up, or from up to right) and repeat the process.

You don't like to change your direction too much, so you will make no more than $n - 1$ direction changes.

As a result, your path will be a polygonal chain from $(0, 0)$ to $(n, n)$, consisting of at most $n$ line segments where each segment has positive integer length and vertical and horizontal segments alternate.

Not all paths are equal. You have $n$ integers $c_1, c_2, \dots, c_n$ where $c_i$ is the cost of the $i$-th segment.

Using these costs we can define the cost of the path as the sum of lengths of the segments of this path multiplied by their cost, i. e. if the path consists of $k$ segments ($k \le n$), then the cost of the path is equal to $\sum\limits_{i=1}^{k}{c_i \cdot length_i}$ (segments are numbered from $1$ to $k$ in the order they are in the path).

Find the path of the minimum cost and print its cost.

假设你站在 $XY$-平面上的点 $(0, 0)$ 处，希望到达点 $(n, n)$。

你只能朝以下两个方向移动：

• 向右，即水平向右移动（使你的 $x$ 坐标增大）；
• 向上，即垂直向上移动（使你的 $y$ 坐标增大）。

换言之，你的路径具有如下结构：

• 起初，你选择向右或向上移动；
• 然后你在所选方向上移动某个正整数距离（各次移动的距离可独立选取）；
• 接着你改变方向（从向右变为向上，或从向上变为向右），并重复该过程。

你不喜欢频繁改变方向，因此最多只允许进行 $n - 1$ 次方向改变。

因此，你的路径是一条从 $(0, 0)$ 到 $(n, n)$ 的折线，由至多 $n$ 条线段组成；每条线段长度为正整数，且竖直线段与水平线段交替出现。

并非所有路径都等价。你拥有 $n$ 个整数 $c_1, c_2, \dots, c_n$，其中 $c_i$ 表示第 $i$ 条线段的单位长度代价。

利用这些代价，我们可定义整条路径的总代价为：路径中各线段长度与其对应代价的乘积之和。即，若路径由 $k$ 条线段组成（$k \le n$），则其总代价为 $\sum\limits_{i=1}^{k}{c_i \cdot \text{length}_i}$（线段按路径中出现顺序编号为 $1$ 至 $k$）。

请找出总代价最小的路径，并输出该最小代价。

The first line contains the single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($2 \le n \le 10^5$).

The second line of each test case contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$) — the costs of each segment.

It's guaranteed that the total sum of $n$ doesn't exceed $10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le 10^9$）—— 各段的费用。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case, print the minimum possible cost of the path from $(0, 0)$ to $(n, n)$ consisting of at most $n$ alternating segments.

对于每个测试用例，输出从 $(0, 0)$ 到 $(n, n)$ 的路径的最小可能代价，该路径由至多 $n$ 个交替线段组成。

In the first test case, to reach $(2, 2)$ you need to make at least one turn, so your path will consist of exactly $2$ segments: one horizontal of length $2$ and one vertical of length $2$. The cost of the path will be equal to $2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202$.

In the second test case, one of the optimal paths consists of $3$ segments: the first segment of length $1$, the second segment of length $3$ and the third segment of length $2$.

The cost of the path is $1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13$.

In the third test case, one of the optimal paths consists of $4$ segments: the first segment of length $1$, the second one — $1$, the third one — $4$, the fourth one — $4$. The cost of the path is $1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19$.

在第一个测试用例中，要到达点 $(2, 2)$，至少需要一次转向，因此路径恰好由 $2$ 段组成：一段长度为 $2$ 的水平线段和一段长度为 $2$ 的垂直线段。该路径的代价为 $2 \cdot c_1 + 2 \cdot c_2 = 26 + 176 = 202$。

在第二个测试用例中，一条最优路径由 $3$ 段组成：第一段长度为 $1$，第二段长度为 $3$，第三段长度为 $2$。

该路径的代价为 $1 \cdot 2 + 3 \cdot 3 + 2 \cdot 1 = 13$。

在第三个测试用例中，一条最优路径由 $4$ 段组成：第一段长度为 $1$，第二段长度为 $1$，第三段长度为 $4$，第四段长度为 $4$。该路径的代价为 $1 \cdot 4 + 1 \cdot 3 + 4 \cdot 2 + 4 \cdot 1 = 19$。