C. Равные значения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан массив $$$a_1, a_2, \dots, a_n$$$, состоящий из $$$n$$$ целых чисел.

За одну операцию с ним разрешается проделать одно из следующих действий:

  • Выбрать позицию $$$i$$$ ($$$1 \lt i \le n$$$) и сделать все элементы слева от $$$i$$$ равными $$$a_i$$$. То есть, присвоить всем $$$a_j$$$ ($$$1 \le j \lt i$$$) значение $$$a_i$$$. Стоимость такой операции равна $$$(i - 1) \cdot a_i$$$.
  • Выбрать позицию $$$i$$$ ($$$1 \le i \lt n$$$) и сделать все элементы справа от $$$i$$$ равными $$$a_i$$$. То есть, присвоить всем $$$a_j$$$ ($$$i \lt j \le n$$$) значение $$$a_i$$$. Стоимость такой операции равна $$$(n - i) \cdot a_i$$$.

Обратите внимание, что элементы, затронутые операцией, могут уже быть равны $$$a_i$$$, но стоимость от этого не поменяется.

Разрешается проделать произвольное количество операций (в том числе ноль). За какую минимальную суммарную стоимость можно сделать все элементы массива одинаковыми?

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — минимальную суммарную стоимость операций, чтобы сделать все элементы массива одинаковыми.

Пример
Входные данные
3
4
2 4 1 3
3
1 1 1
10
7 5 5 5 10 9 9 4 6 10
Выходные данные
3
0
35
Примечание

В первом наборе входных данных можно применить операцию дважды:

  • выбрать $$$i = 3$$$ и сделать все элементы слева от него равными ему, стоимость будет $$$2 \cdot 1 = 2$$$;
  • выбрать $$$i = 3$$$ и сделать все элементы справа от него равными ему, стоимость будет $$$1 \cdot 1 = 1$$$.

Суммарная стоимость равна $$$2 + 1 = 3$$$.

Во втором наборе все элементы уже равны, поэтому можно не применять операции.