D1. Minimum with Left Shift (Easy Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy version of this problem. In this version, you need to find the minimum possible cost.

Sanjay wanted to solve a problem, but since he had no friends, he handed it over to you. Please solve it for him.

Given an array $$$a$$$ of length $$$n$$$, the cost $$$c$$$ is defined as:

$$$$$$ c = a_1 \cdot 1 + a_2 \cdot 2 + \dots + a_{n} \cdot n $$$$$$

Your task is to find the minimum possible cost that can be achieved after applying any number of left cyclic shift operations on the array.

A left cyclic shift operation moves each element of the array one position to the left, with the first element moving to the end.

For example, $$$$$$ a = [1, 2, 3, 4] \quad$$$$$$ after one left shift becomes $$$$$$a = [2, 3, 4, 1] $$$$$$

Input
  • The first line contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
  • For each test case:
    • The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the size of the array.
    • The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ $$$(-10^9 \leq a_i \leq 10^9)$$$ — the elements of the array.
  • The sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
Output
  • For each test case, print a single integer — the minimum cost in all possible left cyclic shifts of the array.
Example
Input
2
4
1 2 3 4
3
1 -1 1
Output
22
0
Note

In the second test case, after performing $$$2$$$ left cyclic shifts, the array becomes $$$[1, 1, -1]$$$, which results in the minimum cost.