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.


-----Input-----

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$.


-----Output-----

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.


-----Examples-----

Input
3
2
13 88
3
2 3 1
5
4 3 2 1 4
Output
202
13
19


-----Note-----

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$.

Source: codeforces | Difficulty: MEDIUM
Tags: Complete search

Data structures

Mathematics

Greedy algorithms


Solutions:
from math import ceil, floor
t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	x = 0
	ans = c[0] * n + c[1] * n
	i = 2
	a = c[0]
	b = c[1]
	sa = c[0]
	sb = c[1]
	aa = bb = 1
	cura = c[0] * n
	curb = c[1] * n
	for i in range(2, n):
		if x:
			if c[i] < b:
				curb = sb + c[i] * (n - bb)
				ans = min(ans, cura + curb)
				b = c[i]
			else:
				curb = curb - b + c[i]
			bb += 1
			sb += c[i]
		else:
			if c[i] < a:
				cura = sa + c[i] * (n - aa)
				ans = min(ans, cura + curb)
				a = c[i]
			else:
				cura = cura - a + c[i]
			aa += 1
			sa += c[i]
		x ^= 1
	print(ans)


def solve(C, n):
	MUC = [0] * n
	MDC = [0] * n
	minUCost = minDCost = 10 ** 10
	for i in range(n):
		if i % 2 == 0:
			minUCost = min(C[i], minUCost)
		else:
			minDCost = min(C[i], minDCost)
		MUC[i] = minUCost
		MDC[i] = minDCost
	minTotalCost = 10 ** 15
	uStepCostSum = dStepCostSum = 0
	for i in range(n):
		uSteps = (i + 2) // 2
		dSteps = i + 1 - uSteps
		if i % 2 == 0:
			uStepCostSum += C[i]
		else:
			dStepCostSum += C[i]
		totalCost = MUC[i] * (n - uSteps) + uStepCostSum + MDC[i] * (n - dSteps) + dStepCostSum
		minTotalCost = min(totalCost, minTotalCost)
	return minTotalCost
t = int(input())
for tc in range(t):
	n = int(input())
	C = list(map(int, input().split()))
	result = solve(C, n)
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	n1 = 0
	n2 = 0
	mx = float('inf')
	my = float('inf')
	cst = float('inf')
	sum = 0
	for i in range(1, n + 1):
		sum += c[i - 1]
		if i % 2 == 0:
			n1 += 1
			mx = min(mx, c[i - 1])
		else:
			n2 += 1
			my = min(my, c[i - 1])
		cst = min(cst, sum + mx * (n - n1) + my * (n - n2))
	print(cst)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	oc = n
	ec = n
	min_o = float('inf')
	min_e = float('inf')
	res = 0
	ans = float('inf')
	for i in range(n):
		if i % 2 == 0:
			res += l[i]
			ec -= 1
			min_e = min(min_e, l[i])
			ans = min(ans, res + ec * min_e + oc * min_o)
		else:
			res += l[i]
			oc -= 1
			min_o = min(min_o, l[i])
			ans = min(ans, res + ec * min_e + oc * min_o)
	print(ans)


num_test_case = int(input())
for t in range(num_test_case):
	num_segments = int(input())
	segments = [int(x) for x in input().split(' ')]
	min_cost_x_segment = segments[0]
	min_cost_x = min_cost_x_segment * num_segments
	min_cost_y_segment = segments[1]
	min_cost_y = min_cost_y_segment * num_segments
	ans = min_cost_x + min_cost_y
	for k in range(2, num_segments):
		if k % 2 == 0:
			if segments[k] < min_cost_x_segment:
				min_cost_x -= (num_segments - k // 2) * (min_cost_x_segment - segments[k])
				min_cost_x_segment = segments[k]
			else:
				min_cost_x += segments[k] - min_cost_x_segment
		elif segments[k] < min_cost_y_segment:
			min_cost_y -= (num_segments - k // 2) * (min_cost_y_segment - segments[k])
			min_cost_y_segment = segments[k]
		else:
			min_cost_y += segments[k] - min_cost_y_segment
		ans = min(ans, min_cost_x + min_cost_y)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = n * (a[0] + a[1])
	mnx = a[0]
	mny = a[1]
	cntx = 1
	cnty = 1
	sx = a[0]
	sy = a[1]
	for i in range(2, n):
		if i % 2 == 0:
			mnx = min(mnx, a[i])
			sx += a[i]
			cntx += 1
		else:
			mny = min(mny, a[i])
			sy += a[i]
			cnty += 1
		ans = min(ans, sx + sy + mnx * (n - cntx) + mny * (n - cnty))
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	tmp = 0
	(nx, ny) = (n, n)
	min_x = math.inf
	min_y = math.inf
	cost = 0
	ans = math.inf
	c = list(map(int, input().split()))
	for i in range(1, n + 1):
		tmp = c[i - 1]
		if i & 1:
			min_x = min(min_x, tmp)
			nx -= 1
		else:
			min_y = min(min_y, tmp)
			ny -= 1
		cost += tmp
		if i > 1:
			ans = min(ans, cost + nx * min_x + ny * min_y)
	print(ans)


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]
for _ in range(Int()):
	n = Int()
	c = array()
	oddCost = c[1]
	evenCost = c[0]
	ans = n * oddCost + n * evenCost
	(odd, even) = (n - 1, n - 1)
	cur = oddCost + evenCost
	for i in range(2, n):
		if i % 2:
			oddCost = min(oddCost, c[i])
			odd -= 1
			extra = evenCost
		else:
			evenCost = min(evenCost, c[i])
			even -= 1
			extra = oddCost
		cur += c[i]
		ans = min(ans, cur + odd * oddCost + even * evenCost)
	print(ans)


def main(n, l):
	minim = n * l[0] + n * l[1]
	min_odd = sum_odd = l[1]
	min_even = sum_even = l[0]
	even_count = odd_count = 1
	for i in range(2, n):
		if i % 2 == 0:
			min_even = min(min_even, l[i])
			sum_even += l[i]
			even_count += 1
		else:
			min_odd = min(min_odd, l[i])
			sum_odd += l[i]
			odd_count += 1
		minim = min(minim, sum_even + (n - even_count) * min_even + sum_odd + (n - odd_count) * min_odd)
	print(minim)
nn = int(input())
for _ in range(nn):
	n = int(input())
	l = [int(s) for s in input().split()]
	main(n, l)


def solve(n, arr):
	mnm = [0] * n
	mnm[0] = arr[0]
	mnm[1] = arr[1]
	sm = [0] * n
	sm[0] = arr[0]
	sm[1] = arr[1]
	for i in range(2, n):
		mnm[i] = min(arr[i], mnm[i - 2])
		sm[i] = arr[i] + sm[i - 2]
	m = float('inf')
	for i in range(n - 1):
		x = sm[i] + sm[i + 1]
		if i % 2 == 0:
			i1 = i // 2 + 1
			x += (n - i1) * (mnm[i] + mnm[i + 1])
		else:
			i1 = i // 2 + 1
			i2 = i1 + 1
			x += (n - i1) * mnm[i] + (n - i2) * mnm[i + 1]
		if x < m:
			m = x
	return m
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	print(solve(n, arr))


import math

def main():
	n = int(input())
	c = list(map(int, input().split()))
	mins = [math.inf] * 2
	reminders = [n] * 2
	summ = 0
	ans = math.inf
	for i in range(n):
		mins[i % 2] = min(mins[i % 2], c[i])
		reminders[i % 2] -= 1
		summ += c[i]
		ans = min(ans, summ + reminders[0] * mins[0] + reminders[1] * mins[1])
	print(ans)
t = int(input())
for i in range(t):
	main()


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		c = list(map(int, input().split()))
		if n == 2:
			print(2 * (c[0] + c[1]))
		else:
			o_min = c[0]
			e_min = c[1]
			o_sum = c[0]
			e_sum = c[1]
			o_min_i = 0
			e_min_i = 1
			ans = n * (c[0] + c[1])
			for k in range(2, n):
				if k % 2 == 0:
					if c[k] < o_min:
						o_min = c[k]
						o_min_i = k
					o_sum += c[k]
				else:
					if c[k] < e_min:
						e_min = c[k]
						e_min_i = k
					e_sum += c[k]
				ans = min(ans, e_sum + o_sum + c[e_min_i] * (n - (k + 1) // 2) + c[o_min_i] * (n - (k + 2) // 2))
			print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	temp_cost = c[0] + c[1]
	cost = temp_cost * n
	a = c[0]
	b = c[1]
	(m0, m1) = (n - 1, n - 1)
	for k in range(2, n):
		temp_cost += c[k]
		if k % 2 == 1:
			m1 -= 1
			b = min(b, c[k])
		else:
			m0 -= 1
			a = min(a, c[k])
		cost = min(cost, temp_cost + a * m0 + b * m1)
	print(cost)


for s in [*open(0)][2::2]:
	l = [*map(int, s.split())]
	q = l[::2]
	qn = len(q)
	w = l[1::2]
	wn = len(w)
	n = len(l)
	c = []
	s = [0, 0]
	m = [1000000000000000.0, 1000000000000000.0]
	p = [n, n]
	for i in range(n):
		x = i & 1
		m[x] = min(m[x], l[i])
		s[x] += l[i]
		p[x] -= 1
		c += [s[x] + p[x] * m[x]]
	print(min((x + y for (x, y) in zip(c, c[1:]))))


import sys
from math import ceil, floor, sqrt
from collections import defaultdict

def read_generator():
	while True:
		tokens = sys.stdin.readline().rstrip().split(' ')
		for t in tokens:
			yield t
reader = read_generator()

def read():
	return next(reader)

def readint():
	return int(next(reader))

def readfloat():
	return float(next(reader))

def readline():
	return input()

def readlistint(n):
	return [readint() for _ in range(n)]

def readliststr(n):
	return [read() for _ in range(n)]

def readlistfloat(n):
	return [readfloat() for _ in range(n)]

def zfunc(s):
	z = [0] * len(s)
	l = 0
	r = 0
	for i in range(1, len(s)):
		if i <= r:
			z[i] = min(z[i - l], r - i + 1)
		while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
			z[i] += 1
		if r < i + z[i] - 1:
			l = i
			r = i + z[i] - 1
	return z

def solve(c, n):
	m = [c[0], c[1]]
	res = n * c[0] + n * c[1]
	s = [c[0], c[1]]
	cnt = [1, 1]
	for i in range(2, n):
		if i % 2 == 0:
			m[0] = min(m[0], c[i])
			s[0] += c[i]
			cnt[0] += 1
		else:
			m[1] = min(m[1], c[i])
			s[1] += c[i]
			cnt[1] += 1
		res = min(res, s[0] - m[0] + (s[1] - m[1]) + (n - cnt[0] + 1) * m[0] + (n - cnt[1] + 1) * m[1])
	return res
tests = readint()
for test in range(1, tests + 1):
	n = readint()
	c = readlistint(n)
	print(solve(c, n))


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	a = [[], []]
	for (i, x) in enumerate(c):
		a[i % 2].append(x)
	ma = [a[0].copy(), a[1].copy()]
	ms = [a[0].copy(), a[1].copy()]
	ma[0][0] = a[0][0]
	ms[0][0] = a[0][0]
	for i in range(1, len(a[0])):
		ms[0][i] = ms[0][i - 1] + a[0][i]
		ma[0][i] = min(ma[0][i - 1], a[0][i])
	ms[1][0] = a[1][0]
	ma[1][0] = a[1][0]
	for i in range(1, len(a[1])):
		ms[1][i] = ms[1][i - 1] + a[1][i]
		ma[1][i] = min(ma[1][i - 1], a[1][i])
	res = None
	for i in range(1, n):
		d1 = ms[0][i // 2] - ma[0][i // 2] + ma[0][i // 2] * (n - i // 2)
		d2 = ms[1][(i - 1) // 2] - ma[1][(i - 1) // 2] + ma[1][(i - 1) // 2] * (n - (i - 1) // 2)
		cur = d1 + d2
		if res is None or res > cur:
			res = cur
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	h = []
	v = []
	for i in range(n):
		if i % 2 == 0:
			h.append(l[i])
		else:
			v.append(l[i])
	hl = len(h)
	hv = len(v)
	p = n * (h[0] + v[0])
	hmin = h[0]
	vmin = v[0]
	mm = p
	i = 1
	j = 1
	while i < hl or j < hv:
		if h[i] < hmin:
			pp = p - hmin * (n - i) + (n - i) * h[i]
			hmin = h[i]
		else:
			pp = p - hmin + h[i]
		p = pp
		if p < mm:
			mm = p
		if j < hv:
			if v[i] < vmin:
				pp = p - vmin * (n - j) + (n - j) * v[j]
				vmin = v[j]
			else:
				pp = p - vmin + v[i]
			p = pp
			if p < mm:
				mm = p
		i = min(i + 1, hl)
		j = min(j + 1, hv)
	print(mm)


import heapq
t = int(input())
for i in range(t):
	n = int(input())
	c = [int(j) for j in input().split()]
	(a, b) = (c[0::2], c[1::2])
	(a1, b1) = ([], [])
	a3 = []
	for a2 in a:
		heapq.heappush(a3, a2)
		a1.append(a3[0])
	a3 = []
	for a2 in b:
		heapq.heappush(a3, a2)
		b1.append(a3[0])
	(suma, sumb) = (sum(a), sum(b))
	(ta, tb) = (len(a) - 1, len(b) - 1)
	res = suma + sumb + (n - ta - 1) * a1[ta] + b1[tb] * (n - tb - 1)
	y = res
	if ta == tb:
		sumb -= b.pop()
		tb -= 1
		y = min(y, suma + sumb + a1[ta] * (n - ta - 1) + b1[tb] * (n - tb - 1))
	while ta > 0 or tb > 0:
		if ta > 0:
			suma -= a.pop()
			ta -= 1
			y = min(y, suma + sumb + a1[ta] * (n - ta - 1) + b1[tb] * (n - tb - 1))
		if tb > 0:
			sumb -= b.pop()
			tb -= 1
			y = min(y, suma + sumb + a1[ta] * (n - ta - 1) + b1[tb] * (n - tb - 1))
	print(y)


import os
import sys
from io import BytesIO, IOBase
from collections import Counter

def main():
	for _ in range(int(input())):
		n = int(input())
		c = list(map(int, input().split()))
		(x, y, u, v, mi) = (c[0], c[1], c[0], c[1], c[0] * n + c[1] * n)
		for i in range(2, n):
			if i % 2:
				y = min(y, c[i])
				v += c[i]
			else:
				x = min(x, c[i])
				v += c[i]
			mi = min(mi, x * (n - i // 2) + u - x + y * (n - i // 2 + (i % 2 == 0)) + v - y)
		print(mi)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(list(map(int, input().split())))
	dp = [0] * n
	dp[0] = float('inf')
	mn1 = l[0]
	mn2 = l[1]
	sm = l[0] + l[1]
	dp[1] = l[0] * n + l[1] * n
	for i in range(2, n):
		if i % 2 == 0:
			mn1 = min(mn1, l[i])
			sm += l[i]
			dp[i] = sm + (n - 1 - i // 2) * mn1 + (n - i // 2) * mn2
		else:
			mn2 = min(mn2, l[i])
			sm += l[i]
			dp[i] = sm + (n - 1 - i // 2) * mn2 + (n - 1 - i // 2) * mn1
	print(min(dp))


from math import ceil
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split(' ')))
	dp = [0] * (n + 1)
	dp[2] = ((c[0], 0), (c[1], 0))
	minprice = n * c[0] + n * c[1]
	for i in range(3, n + 1):
		if i % 2 == 0:
			(statx, pstaty) = dp[i - 1]
			if c[i - 1] < pstaty[0]:
				staty = (c[i - 1], pstaty[1] + pstaty[0])
			else:
				staty = (pstaty[0], pstaty[1] + c[i - 1])
		else:
			(pstatx, staty) = dp[i - 1]
			if c[i - 1] < pstatx[0]:
				statx = (c[i - 1], pstatx[1] + pstatx[0])
			else:
				statx = (pstatx[0], pstatx[1] + c[i - 1])
		dp[i] = (statx, staty)
		price = (n - (i - 1) // 2) * statx[0] + statx[1] + (n - (i - 2) // 2) * staty[0] + staty[1]
		minprice = min(minprice, price)
	print(minprice)


def path(arr):
	(ne, no) = (len(arr), len(arr))
	(me, mo) = (float('inf'), float('inf'))
	(s, ans) = (0, float('inf'))
	for i in range(len(arr)):
		if i % 2 == 0:
			ne -= 1
			me = min(me, arr[i])
			s += arr[i]
		else:
			no -= 1
			mo = min(mo, arr[i])
			s += arr[i]
		ans = min(ans, s + me * ne + mo * no)
	return ans
for i in range(int(input())):
	a = input()
	lst = list(map(int, input().strip().split()))
	print(path(lst))


for s in [*open(0)][2::2]:
	a = s.split()
	i = len(a)
	j = 0
	r = p = 1000000000000000.0
	b = [0, 0]
	c = [p, p]
	for x in map(int, a):
		j ^= 1
		i -= j
		b[j] += x
		c[j] = min(c[j], x)
		x = b[j] + c[j] * i
		r = min(r, p + x)
		p = x
	print(r)


import os
import sys
from io import BytesIO, IOBase
import heapq as h
import bisect
import math as mt
from types import GeneratorType
BUFSIZE = 8192

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
import sys
from math import ceil, log2
INT_MAX = sys.maxsize
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def minVal(x, y):
	return x if x < y else y

def getMid(s, e):
	return s + (e - s) // 2

def RMQUtil(st, ss, se, qs, qe, index):
	if qs <= ss and qe >= se:
		return st[index]
	if se < qs or ss > qe:
		return INT_MAX
	mid = getMid(ss, se)
	return minVal(RMQUtil(st, ss, mid, qs, qe, 2 * index + 1), RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2))

def RMQ(st, n, qs, qe):
	if qs < 0 or qe > n - 1 or qs > qe:
		print('Invalid Input')
		return -1
	return RMQUtil(st, 0, n - 1, qs, qe, 0)

def constructSTUtil(arr, ss, se, st, si):
	if ss == se:
		st[si] = arr[ss]
		return arr[ss]
	mid = getMid(ss, se)
	st[si] = minVal(constructSTUtil(arr, ss, mid, st, si * 2 + 1), constructSTUtil(arr, mid + 1, se, st, si * 2 + 2))
	return st[si]

def constructST(arr, n):
	x = int(ceil(log2(n)))
	max_size = 2 * int(2 ** x) - 1
	st = [0] * max_size
	constructSTUtil(arr, 0, n - 1, st, 0)
	return st
MOD = 10 ** 9 + 7
mod = 10 ** 9 + 7
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def z_array(s1):
	n = len(s1)
	z = [0] * n
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and s1[r - l] == s1[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and s1[r - l] == s1[r]:
					r += 1
				z[i] = r - l
				r -= 1
	return z

def fs(x):
	if x < 2:
		return 0
	return x * (x - 1) // 2
t = int(input())

def solve():
	min1 = l[0]
	min2 = l[1]
	cnt = 0
	ans = n * min1 + n * min2
	ans1 = min1 + min2
	for i in range(2, n):
		ans1 += l[i]
		if cnt % 2 == 0:
			min1 = min(l[i], min1)
			ans = min(ans, ans1 + (n - (i + 2) // 2) * min1 + (n - (i + 1) // 2) * min2)
		else:
			min2 = min(l[i], min2)
			ans = min(ans, ans1 + (n - (i + 2) // 2) * min2 + (n - (i + 1) // 2) * min1)
		cnt += 1
	return ans
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(solve())


for _ in range(int(input())):
	n = int(input())
	c = [int(x) for x in input().split()]
	pre = [0] * n
	pre[0] = c[0]
	for i in range(1, n):
		pre[i] = pre[i - 1] + c[i]
	lmin2 = [[c[0], c[1]]]
	l1 = c[0]
	l2 = c[1]
	res = n * (l1 + l2)
	for i in range(2, n):
		if i + 1 & 1:
			l1 = min(l1, c[i])
		else:
			l2 = min(l2, c[i])
		seg1 = (i + 2) // 2
		seg2 = i + 1 - seg1
		seg1 -= 1
		seg2 -= 1
		res = min(res, l1 * (n - seg1) + l2 * (n - seg2) + pre[i] - (l1 + l2))
	print(res)


import math
t = int(input())
for x in range(0, t):
	n = int(input())
	arr = [int(a) for a in input().split()]
	v1 = []
	h1 = []
	for i in range(0, n):
		if i % 2 == 0:
			v1.append(arr[i])
		else:
			h1.append(arr[i])
	l1 = len(v1)
	l2 = len(h1)
	v2 = []
	h2 = []
	min1 = v1[0]
	min2 = h1[0]
	for i in range(0, l1):
		if v1[i] < min1:
			min1 = v1[i]
		v2.append(min1)
	for i in range(0, l2):
		if h1[i] < min2:
			min2 = h1[i]
		h2.append(min2)
	for i in range(1, l1):
		v1[i] = v1[i] + v1[i - 1]
	for i in range(1, l2):
		h1[i] = h1[i] + h1[i - 1]
	for i in range(0, l1):
		v1[i] = v1[i] + (n - i - 1) * v2[i]
	for i in range(0, l2):
		h1[i] = h1[i] + (n - i - 1) * h2[i]
	final = []
	i = 0
	while i < l1 and i < l2:
		final.append(v1[i] + h1[i])
		if i + 1 < l1:
			final.append(v1[i + 1] + h1[i])
		i = i + 1
	print(min(final))


t = int(input())
for _ in range(t):
	n = int(input())
	cost = list(map(int, input().split()))
	evenSum = cost[0]
	oddSum = cost[1]
	evenMin = cost[0]
	oddMin = cost[1]
	evenCnt = 1
	oddCnt = 1
	ans = evenSum + evenMin * (n - evenCnt) + oddSum + oddMin * (n - oddCnt)
	for i in range(2, n):
		if i % 2 == 0:
			evenSum += cost[i]
			evenCnt += 1
			evenMin = min(evenMin, cost[i])
		else:
			oddSum += cost[i]
			oddCnt += 1
			oddMin = min(oddMin, cost[i])
		ans = min(ans, evenSum + evenMin * (n - evenCnt) + oddSum + oddMin * (n - oddCnt))
	print(ans)


from itertools import accumulate
from sys import stdin, gettrace
if gettrace():

	def inputi():
		return input()
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def solve():
	n = int(input())
	cc = [int(a) for a in input().split()]
	ccs = list(accumulate(cc))
	ccmr = list(accumulate(cc[::2], func=lambda a, b: min(a, b)))
	ccmu = list(accumulate(cc[1::2], func=lambda a, b: min(a, b)))
	costs = [ccs[i] + ccmr[i // 2] * (n - i // 2 - 1) + ccmu[(i - 1) // 2] * (n - (i - 1) // 2 - 1) for i in range(1, n)]
	res = min(costs)
	print(res)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


import sys

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
t = II()
for s1 in range(t):
	n = II()
	l = LI()
	ans = l[0] * n + l[1] * n
	cur = l[0] + l[1]
	curmin = l[0]
	curminh = l[1]
	for i in range(2, n):
		if i % 2 == 0:
			curmin = min(curmin, l[i])
		else:
			curminh = min(curminh, l[i])
		cur += l[i]
		if (i + 1) % 2 == 0:
			if curmin * (n - (i + 1) // 2) + curminh * (n - (i + 1) // 2) + cur < ans:
				ans = curmin * (n - (i + 1) // 2) + curminh * (n - (i + 1) // 2) + cur
		elif curmin * (n - (i + 1) // 2 - 1) + curminh * (n - (i + 1) // 2) + cur < ans:
			ans = curmin * (n - (i + 1) // 2 - 1) + curminh * (n - (i + 1) // 2) + cur
	print(ans)


import sys
input = sys.stdin.readline

def I():
	return input().strip()

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, combinations, groupby
for _ in range(II()):
	n = II()
	a = LI()
	ans = n * a[0] + n * a[1]
	min1 = a[0]
	car1 = n - 1
	min2 = a[1]
	car2 = n - 1
	anslist = [ans]
	for i in range(2, n):
		if i % 2 == 0:
			if a[i] < min1:
				ans -= car1 * (min1 - a[i])
				min1 = a[i]
			else:
				ans += a[i]
				ans -= min1
			car1 -= 1
			anslist.append(ans)
		else:
			if a[i] < min2:
				ans -= car2 * (min2 - a[i])
				min2 = a[i]
			else:
				ans += a[i]
				ans -= min2
			car2 -= 1
			anslist.append(ans)
	print(min(anslist))


import sys

def load_sys():
	return sys.stdin.readlines()

def load_local():
	with open('input.txt', 'r') as f:
		input = f.readlines()
	return input

def f(n, costs):
	odd_sum = 0
	even_sum = 0
	odd_cnt = 0
	even_cnt = 0
	odd_mn = float('inf')
	even_mn = float('inf')
	ans = float('inf')
	for i in range(len(costs)):
		if i % 2 == 0:
			even_sum += costs[i]
			even_mn = min(even_mn, costs[i])
			even_cnt += 1
		else:
			odd_sum += costs[i]
			odd_mn = min(odd_mn, costs[i])
			odd_cnt += 1
		cost = odd_sum - odd_mn + (n - odd_cnt + 1) * odd_mn + even_sum - even_mn + (n - even_cnt + 1) * even_mn
		ans = min(ans, cost)
	return ans
input = load_sys()
for i in range(1, len(input), 2):
	n = int(input[i])
	costs = [int(x) for x in input[i + 1].split()]
	print(f(n, costs))


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	upMin = array[1]
	upCount = 0
	rightMin = array[0]
	rightCount = 0
	minCost = float('inf')
	oddSum = 0
	evenSum = 0
	for (idx, val) in enumerate(array, 1):
		if idx % 2 == 0:
			upCount += 1
			upMin = min(upMin, val)
			evenSum += val
		else:
			rightCount += 1
			rightMin = min(rightMin, val)
			oddSum += val
		minCost = min(minCost, upMin * (n - upCount) + evenSum + rightMin * (n - rightCount) + oddSum)
	print(minCost)


def cum_sum(in_list):
	for i in range(1, len(in_list)):
		in_list[i] += in_list[i - 1]
	return in_list

def move(n, costs):
	cum_sum = costs[0]
	(even_min, even_cnt) = (costs[0], 1)
	(odd_min, odd_cnt) = (10 ** 9 + 1, 0)
	tl_cnt_odd = n // 2
	tl_cnt_even = n - tl_cnt_odd
	best = None
	for i in range(1, len(costs)):
		cum_sum += costs[i]
		is_even = i % 2 == 0
		if is_even:
			even_cnt += 1
			if costs[i] < even_min:
				even_min = costs[i]
		else:
			odd_cnt += 1
			if costs[i] < odd_min:
				odd_min = costs[i]
		total = cum_sum + (n - even_cnt) * even_min + (n - odd_cnt) * odd_min
		if best is None or total < best:
			best = total
	print(best)
num = int(input())
for _ in range(num):
	n = int(input())
	costs = [int(el) for el in input().split()]
	move(n, costs)


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def A(n):
	return [0] * n

def AI(n, x):
	return [x] * n

def A2(n, m):
	return [[0] * m for i in range(n)]

def G(n):
	return [[] for i in range(n)]

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
mod = 10 ** 9 + 7
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	fact(x, mod)
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa.reverse()

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def floorsum(a, b, c, n):
	if a == 0:
		return b // c * (n + 1)
	if a >= c or b >= c:
		return floorsum(a % c, b % c, c, n) + b // c * (n + 1) + a // c * n * (n + 1) // 2
	m = (a * n + b) // c
	return n * m - floorsum(c, c - b - 1, a, m - 1)

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

def lowbit(n):
	return n & -n

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class ST:

	def __init__(self, arr):
		n = len(arr)
		mx = n.bit_length()
		self.st = [[0] * mx for i in range(n)]
		for i in range(n):
			self.st[i][0] = arr[i]
		for j in range(1, mx):
			for i in range(n - (1 << j) + 1):
				self.st[i][j] = max(self.st[i][j - 1], self.st[i + (1 << j - 1)][j - 1])

	def query(self, l, r):
		if l > r:
			return -inf
		s = (r + 1 - l).bit_length() - 1
		return max(self.st[l][s], self.st[r - (1 << s) + 1][s])

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		seen.add(u)
		for (v, w) in graph[u]:
			if v not in d or d[v] > d[u] + w:
				d[v] = d[u] + w
				heappush(heap, (d[v], v))
	return d

def bell(s, g):
	dis = AI(n, inf)
	dis[s] = 0
	for i in range(n - 1):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
	change = A(n)
	for i in range(n):
		for (u, v, w) in edge:
			if dis[v] > dis[u] + w:
				dis[v] = dis[u] + w
				change[v] = 1
	return dis

def lcm(a, b):
	return a * b // gcd(a, b)

def lis(nums):
	res = []
	for k in nums:
		i = bisect.bisect_left(res, k)
		if i == len(res):
			res.append(k)
		else:
			res[i] = k
	return len(res)

def RP(nums):
	n = len(nums)
	s = set(nums)
	d = {}
	for (i, k) in enumerate(sorted(s), 1):
		d[k] = i
	bi = BIT([0] * (len(s) + 1))
	ans = 0
	for i in range(n - 1, -1, -1):
		ans += bi.query(d[nums[i]] - 1)
		bi.update(d[nums[i]], 1)
	return ans

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

def nb(i, j, n, m):
	for (ni, nj) in [[i + 1, j], [i - 1, j], [i, j - 1], [i, j + 1]]:
		if 0 <= ni < n and 0 <= nj < m:
			yield (ni, nj)

def topo(n):
	q = deque()
	res = []
	for i in range(1, n + 1):
		if ind[i] == 0:
			q.append(i)
			res.append(i)
	while q:
		u = q.popleft()
		for v in g[u]:
			ind[v] -= 1
			if ind[v] == 0:
				q.append(v)
				res.append(v)
	return res

@bootstrap
def gdfs(r, p):
	if len(g[r]) == 1 and p != -1:
		yield None
	for ch in g[r]:
		if ch != p:
			yield gdfs(ch, r)
	yield None
t = N()
for i in range(t):
	n = N()
	c = RLL()
	mi = c.copy()
	dp = [inf] * n
	dp[0] = c[0] * n
	dp[1] = c[1] * n
	pre = A(n)
	pre[0] = c[0]
	pre[1] = c[1]
	ans = dp[0] + dp[1]
	for i in range(2, n):
		pre[i] = pre[i - 2] + c[i]
		mi[i] = min(mi[i], mi[i - 2])
		cur = mi[i] * (n - ((i - (i & 1)) // 2 + 1)) + pre[i]
		dp[i] = cur
		ans = min(ans, dp[i] + dp[i - 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	cx = c[1] * n
	cy = c[0] * n
	odd_sum = min_odd = c[1]
	even_sum = min_even = c[0]
	odds = evens = 1
	min_cost = cx + cy
	for i in range(2, n):
		if i & 1:
			odds += 1
			odd_sum += c[i]
			min_odd = min(min_odd, c[i])
			rest_sum = odd_sum - min_odd
			rem_dist = n - odds + 1
			cx = rest_sum + rem_dist * min_odd
		else:
			evens += 1
			even_sum += c[i]
			min_even = min(min_even, c[i])
			rest_sum = even_sum - min_even
			rem_dist = n - evens + 1
			cy = rest_sum + rem_dist * min_even
		min_cost = min(min_cost, cx + cy)
	print(min_cost)


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		N = int(input())
		C = [int(x) for x in input().split()]
		ans = float('inf')
		mi_even = float('inf')
		mi_odd = float('inf')
		total_even = 0
		total_odd = 0
		cnt_even = 0
		cnt_odd = 0
		for i in range(N):
			if i % 2 == 0:
				total_even += C[i]
				cnt_even += 1
				mi_even = min(mi_even, C[i])
			else:
				total_odd += C[i]
				cnt_odd += 1
				mi_odd = min(mi_odd, C[i])
			if i >= 1:
				tmp = total_even + total_odd
				tmp += (N - cnt_even) * mi_even
				tmp += (N - cnt_odd) * mi_odd
				ans = min(ans, tmp)
		print(ans)
main()


def calMinCost(C, n):
	MinUCost = [0] * n
	MinDCost = [0] * n
	uMinCost = dMinCost = 10 ** 10
	for i in range(n):
		if i % 2 == 0:
			uMinCost = min(C[i], uMinCost)
		else:
			dMinCost = min(C[i], dMinCost)
		MinUCost[i] = uMinCost
		MinDCost[i] = dMinCost
	minCost = 10 ** 15
	uCostAdd = 0
	dCostAdd = 0
	for i in range(n):
		uNext = (i + 2) // 2
		dNex = i + 1 - uNext
		if i % 2 == 0:
			uCostAdd = C[i] + uCostAdd
		else:
			dCostAdd = C[i] + dCostAdd
		cotTotal = MinUCost[i] * (n - uNext) + uCostAdd + MinDCost[i] * (n - dNex) + dCostAdd
		minCost = min(cotTotal, minCost)
	return minCost
numTest = int(input())
for i in range(numTest):
	cn = int(input())
	data = input().split()
	finalData = [int(x) for x in data]
	result = calMinCost(finalData, cn)
	print(result)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	min1 = a[0]
	min2 = a[1]
	temp1 = min1 * n
	temp2 = min2 * n
	ans = temp1 + temp2
	sm1 = 0
	sm2 = 0
	counter1 = 0
	counter2 = 0
	for i in range(n):
		if i % 2 == 0:
			sm1 += a[i]
			if a[i] < min1:
				min1 = a[i]
			temp1 = sm1 + (n - counter1 - 1) * min1
			counter1 += 1
		else:
			sm2 += a[i]
			if a[i] < min2:
				min2 = a[i]
			temp2 = sm2 + (n - counter2 - 1) * min2
			counter2 += 1
		if temp1 + temp2 < ans:
			ans = temp1 + temp2
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline()

def RL():
	return map(int, sys.stdin.readline().split())

def RLL():
	return list(map(int, sys.stdin.readline().split()))

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from collections import deque as dq
from math import ceil, floor, sqrt, pow, factorial, log2
from collections import Counter
for _ in range(N()):
	n = N()
	l = RLL()
	m1 = l[0]
	m2 = l[1]
	c = l[0] * n + l[1] * n
	pre = [x for x in l]
	for i in range(1, n):
		pre[i] += pre[i - 1]
	for i in range(2, n):
		if i % 2 == 1:
			m2 = min(m2, l[i])
			a = pre[i] - m1 - m2 + m1 * (n - (i - 2) // 2) + m2 * (n - (i - 2) // 2)
			c = min(c, pre[i] - m1 - m2 + m1 * (n - (i - 1) // 2) + m2 * (n - (i - 1) // 2))
		else:
			m1 = min(m1, l[i])
			a = pre[i] - m1 - m2 + m1 * (n - (i - 1) // 2) + m2 * (n - (i - 2) // 2)
			c = min(c, pre[i] - m1 - m2 + m1 * (n - i // 2) + m2 * (n - (i - 2) // 2))
	print(c)


import sys
input = sys.stdin.readline

def print(x, end='\n'):
	sys.stdout.write(str(x) + end)
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().strip().split()))
	total = c[0] + c[1]
	no_odd = 1
	no_even = 1
	min_odd = c[0]
	min_even = c[1]
	ans = total + (n - no_odd) * min_odd + (n - no_even) * min_even
	for i in range(2, n):
		total += c[i]
		if i % 2 == 0:
			no_odd += 1
			min_odd = min(min_odd, c[i])
		else:
			no_even += 1
			min_even = min(min_even, c[i])
		ans = min(ans, total + (n - no_odd) * min_odd + (n - no_even) * min_even)
	print(ans)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	l = arr[0]
	m = arr[1]
	ans = arr[0] * n + arr[1] * n
	r = arr[0] + arr[1]
	t = 1
	s = 1
	for i in range(2, n):
		r += arr[i]
		if i % 2 == 0:
			s += 1
			l = min(l, arr[i])
		else:
			t += 1
			m = min(m, arr[i])
		ans = min(ans, (n - s) * l + (n - t) * m + r)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = [int(x) for x in input().split()]
	(prices, mn_e, mn_o, s) = (10 ** 20, c[0], c[1], c[0])
	for i in range(2, n + 1):
		s += c[i - 1]
		if i % 2 == 0 and i != n:
			mn_e = min(mn_e, c[i])
		elif i % 2 == 1 and i != n:
			mn_o = min(mn_o, c[i])
		price = s + (n - (i + 1) // 2) * mn_e + (n - i // 2) * mn_o
		prices = min(price, prices)
	print(prices)


def solve():
	n = int(input())
	c = list(map(int, input().split()))
	mn = [1000000000.0, 1000000000.0]
	rem = [n, n]
	sm = 0
	ans = 1e+18
	for i in range(n):
		mn[i % 2] = min(mn[i % 2], c[i])
		rem[i % 2] -= 1
		sm += c[i]
		if i > 0:
			temp = sm + mn[0] * rem[0] + mn[1] * rem[1]
			ans = min(ans, temp)
	print(int(ans))
t = int(input())
for _ in range(t):
	solve()


import sys
import math
from bisect import bisect_right as br
from statistics import mode
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	arr = int_arr()
	ans = float('inf')
	cnt_r = 1
	cnt_u = 0
	mn1 = arr[0]
	mn2 = arr[1]
	sm = arr[0]
	for i in range(1, n):
		sm += arr[i]
		if i % 2 == 0:
			cnt_r += 1
			mn1 = min(mn1, arr[i])
			ans = min(ans, (n - cnt_r) * mn1 + (n - cnt_u) * mn2 + sm)
		else:
			cnt_u += 1
			mn2 = min(mn2, arr[i])
			ans = min(ans, (n - cnt_u) * mn2 + (n - cnt_r) * mn1 + sm)
	print(ans)


def main():

	def win(n, weights):
		(evenmin, oddmin) = (weights[0], weights[1])
		(evenp, oddp) = (weights[0], weights[1])
		(evenc, oddc) = (1, 1)
		val = n * (weights[0] + weights[1])
		for i in range(2, n):
			oddp = oddp + i % 2 * weights[i]
			evenp = evenp + (i + 1) % 2 * weights[i]
			if i % 2:
				oddmin = min(weights[i], oddmin)
				oddc += 1
			else:
				evenmin = min(weights[i], evenmin)
				evenc += 1
			newval = evenp + (n - evenc) * evenmin + oddp + (n - oddc) * oddmin
			val = min(val, newval)
		return val
	cases = int(input())
	for case in range(cases):
		n = int(input())
		weights = list(map(int, input().split()))
		print(win(n, weights))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	mc = a[0] * n + a[1] * n
	mec = a[0]
	moc = a[1]
	es = a[0]
	os = 0
	ec = 1
	oc = 0
	for i in range(1, n):
		if i % 2 == 0:
			mec = min(mec, a[i])
			es += a[i]
			ec += 1
		else:
			moc = min(moc, a[i])
			os += a[i]
			oc += 1
		mc = min(mc, es + (n - ec) * mec + os + (n - oc) * moc)
	print(mc)


import sys
import math
from collections import defaultdict, Counter, deque
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = n * (a[0] + a[1])
	l = [a[0], a[1]]
	mio = a[0]
	mie = a[1]
	for j in range(2, n):
		cur = 0
		if j % 2 == 0:
			l[0] += a[j]
			mio = min(mio, a[j])
			cur = mio * (n - j // 2) + l[0] - mio + mie * (n - j // 2 + 1) + l[1] - mie
		else:
			l[1] += a[j]
			mie = min(mie, a[j])
			cur = mio * (n - j // 2) + l[0] - mio + mie * (n - j // 2) + l[1] - mie
		ans = min(ans, cur)
	print(ans)


for s in [*open(0)][2::2]:
	(*a,) = map(int, s.split())
	n = len(a)
	r = p = 1e+18
	b = [p, p] + a
	a = [0, 0] + a
	for i in range(2, n + 2):
		a[i] += a[i - 2]
		b[i] = min(b[i], b[i - 2])
		x = a[i] + b[i] * (n - i // 2)
		r = min(r, p + x)
		p = x
	print(r)


for _ in range(int(input())):
	(n, clist1, clist2, p1, p) = (int(input()), [], [], 0, 0)
	clist = list(map(int, input().split(' ')))
	m1 = m2 = ans1 = float('inf')
	for i in range(n):
		if i & 1:
			clist1.append(clist[i])
			m1 = min(m1, clist[i])
		else:
			clist2.append(clist[i])
			m2 = min(m2, clist[i])
		p += clist[i]
		ans1 = min(ans1, p + m1 * (n - len(clist1)) + m2 * (n - len(clist2)))
	print(ans1)


from sys import stdin
input = stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	c = [int(x) for x in input().split()]
	min_r = c[0]
	min_u = c[1]
	cc = [c[0] + c[1]]
	r = [min_r]
	u = [min_u]
	for i in range(2, n):
		if i % 2 == 0:
			min_r = min(min_r, c[i])
		else:
			min_u = min(min_u, c[i])
		cc.append(cc[-1] + c[i])
		r.append(min_r)
		u.append(min_u)
	ans = float('inf')
	for i in range(len(r)):
		ans = min(ans, cc[i] - r[i] - u[i] + r[i] * (n - (i // 2 + (i % 2 > 0))) + u[i] * (n - i // 2))
	print(ans)


import sys, getpass
import math, random
import functools, itertools, collections, heapq, bisect
from collections import Counter, defaultdict, deque
input = sys.stdin.readline
M9 = 10 ** 9 + 7
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def solve_(lst):
	n = len(lst)
	arr = lst[::2] + [lst[::2][-1]]
	brr = lst[1::2] + [lst[1::2][-1]]
	mina = arr[0]
	minb = brr[0]
	suma = arr[0]
	sumb = brr[0]
	resb = brr[0] * n
	minres = arr[0] * n + brr[0] * n
	for (i, (a, b)) in enumerate(zip(arr[1:], brr[1:]), start=2):
		mina = min(a, mina)
		suma += a
		resa = suma + mina * (n - i)
		minres = min(minres, resa + resb)
		minb = min(b, minb)
		sumb += b
		resb = sumb + minb * (n - i)
		minres = min(minres, resa + resb)
	return minres
for case_num in range(int(input())):
	k = int(input())
	lst = list(map(int, input().split()))
	res = solve(lst)
	print(res)


import sys
t = int(input())
for _t in range(t):
	n = int(input())
	c_inp = [int(e) for e in input().strip().split()]
	minv = float('inf')
	(sum0, min0, len0) = (c_inp[0], c_inp[0], 1)
	(sum1, min1, len1) = (c_inp[1], c_inp[1], 1)
	for k in range(1, n):
		if k != 1:
			if k % 2 == 0:
				sum0 += c_inp[k]
				len0 += 1
				min0 = min(min0, c_inp[k])
			else:
				sum1 += c_inp[k]
				len1 += 1
				min1 = min(min1, c_inp[k])
		minv = min(minv, sum0 + min0 * (n - len0) + sum1 + min1 * (n - len1))
	print(minv)


import sys, math, itertools, random, bisect
from collections import defaultdict
INF = 10 ** 15

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	c = get_array()
	(o, e) = (0, 0)
	(o_sum, e_sum) = (0, 0)
	(o_min, e_min) = (INF, INF)
	(o_ans, e_ans) = (INF, INF)
	ans = INF
	for i in range(n):
		if i & 1:
			o += 1
			o_sum += c[i]
			o_min = min(o_min, c[i])
			o_ans = o_sum + (n - o) * o_min
		else:
			e += 1
			e_sum += c[i]
			e_min = min(e_min, c[i])
			e_ans = e_sum + (n - e) * e_min
		if i:
			ans = min(ans, o_ans + e_ans)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	c1 = 10 ** 9
	c2 = 10 ** 9
	s1 = 0
	s2 = 0
	ans = 10 ** 15
	for i in range(n):
		if i % 2 == 0:
			s1 += c[i]
			if c1 > c[i]:
				c1 = c[i]
		if i % 2 == 1:
			s2 += c[i]
			if c2 > c[i]:
				c2 = c[i]
		if i > 0:
			ret = s1 - c1 + s2 - c2
			ret += c1 * (n - i // 2)
			ret += c2 * (n - (i - 1) // 2)
			if ret < ans:
				ans = ret
	print(ans)


def calMinCost(C, n):
	MinUCost = [0] * n
	MinRCost = [0] * n
	uMinCost = rMinCost = 10 ** 10
	for i in range(n):
		if i % 2 == 0:
			uMinCost = min(C[i], uMinCost)
		else:
			rMinCost = min(C[i], rMinCost)
		MinUCost[i] = uMinCost
		MinRCost[i] = rMinCost
	minCost = 10 ** 15
	uCostAdd = 0
	rCostAdd = 0
	for i in range(n):
		uNext = (i + 2) // 2
		rNext = i + 1 - uNext
		if i % 2 == 0:
			uCostAdd = C[i] + uCostAdd
		else:
			rCostAdd = C[i] + rCostAdd
		cotTotal = MinUCost[i] * (n - uNext) + uCostAdd + MinRCost[i] * (n - rNext) + rCostAdd
		minCost = min(cotTotal, minCost)
	return minCost
numTest = int(input())
for i in range(numTest):
	cn = int(input())
	data = input().split()
	finalData = [int(x) for x in data]
	result = calMinCost(finalData, cn)
	print(result)


import sys
from sys import stdin
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	n = int(stdin.readline())
	c = list(map(int, stdin.readline().split()))
	ans = float('inf')
	anum = 0
	asum = 0
	amin = float('inf')
	bnum = 0
	bsum = 0
	bmin = float('inf')
	for i in range(n):
		if i % 2 == 0:
			anum += 1
			asum += c[i]
			amin = min(amin, c[i])
		else:
			bnum += 1
			bsum += c[i]
			bmin = min(bmin, c[i])
		if i >= 1:
			ans = min(ans, asum + amin * (n - anum) + bsum + bmin * (n - bnum))
	ANS.append(str(ans))
print('\n'.join(ANS))


t = int(input())
for _ in range(t):
	n = int(input())
	costs = input().split()
	costs = [int(item) for item in costs]
	minPathCost = (costs[0] + costs[1]) * n
	horizSum = 0
	vertSum = 0
	minHoriz = 10 ** 10
	minVert = 10 ** 10
	numHoriz = 0
	numVert = 0
	for i in range(n):
		if i % 2 == 0:
			horizSum += costs[i]
			minHoriz = min(minHoriz, costs[i])
			numHoriz += 1
		if i % 2 != 0:
			vertSum += costs[i]
			minVert = min(minVert, costs[i])
			numVert += 1
		goodSum = minHoriz * (n - numHoriz) + minVert * (n - numVert) + horizSum + vertSum
		minPathCost = min(minPathCost, goodSum)
	print(minPathCost)


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	(mas1, mas2) = ([], [])
	(minn1, minn2, ans) = (10000000000, 10000000000, 1000000000000000)
	summ = 0
	for i in range(n):
		summ += c[i]
		if i % 2 == 1:
			minn1 = min(minn1, c[i])
			mas1.append(c[i])
		else:
			minn2 = min(minn2, c[i])
			mas2.append(c[i])
		ans = min(ans, summ + minn1 * (n - len(mas1)) + minn2 * (n - len(mas2)))
	print(ans)


import math
from array import array

def solve(n, C):
	sums = []
	min_even = math.inf
	min_odd = math.inf
	min_e = math.inf
	min_o = math.inf
	even_sum = 0
	even_count = 0
	odd_sum = 0
	odd_count = 0
	for (i, c) in enumerate(C):
		if i % 2 == 0:
			even_sum += c
			even_count += 1
			min_e = min(c, min_e)
			min_even = even_sum + min_e * (n - even_count)
			sums.append(min_odd + min_even)
		else:
			odd_sum += c
			odd_count += 1
			min_o = min(c, min_o)
			min_odd = odd_sum + min_o * (n - odd_count)
			sums.append(min_even + min_odd)
	return min(sums)

def main():
	ans = []
	t = int(input())
	for _ in range(t):
		n = int(input())
		c = list(map(int, input().split(' ')))
		ans.append(solve(n, c))
	for a in ans:
		print(a)
main()


for _ in range(int(input())):
	n = int(input())
	costs = list(map(int, input().split()))
	cum_costs = [0] * n
	min_costs = [10000000000.0] * n
	min_total_cost = 1000000000000000.0
	for i in range(n):
		if i < 2:
			cum_costs[i] = costs[i]
			min_costs[i] = costs[i]
			continue
		cum_costs[i] = cum_costs[i - 2] + costs[i]
		min_costs[i] = min(min_costs[i - 2], costs[i])
	for k in range(2, n + 1):
		k1 = k // 2
		k2 = k1 + k % 2
		i = k - 1
		tmp_cost1 = cum_costs[i - 1] + (n - k1) * min_costs[i - 1]
		tmp_cost2 = cum_costs[i] + (n - k2) * min_costs[i]
		total_cost = tmp_cost1 + tmp_cost2
		min_total_cost = min(min_total_cost, total_cost)
	print(min_total_cost)


import sys
from sys import stdin

def solve(N, C):
	best_cost = N * C[0] + N * C[1]
	cur_cost = N * C[0] + N * C[1]
	min_1 = C[0]
	min_2 = C[1]
	use_min_1 = N + 0
	use_min_2 = N + 0
	for i in range(2, N):
		if i % 2 == 0:
			cost = C[i]
			if cost < min_1:
				cur_cost -= (min_1 - cost) * (use_min_1 - 1)
				min_1 = cost
				if cur_cost < best_cost:
					best_cost = cur_cost
			else:
				cur_cost += cost - min_1
			use_min_1 -= 1
		else:
			cost = C[i]
			if cost < min_2:
				cur_cost -= (min_2 - cost) * (use_min_2 - 1)
				min_2 = cost
				if cur_cost < best_cost:
					best_cost = cur_cost
			else:
				cur_cost += cost - min_2
			use_min_2 -= 1
	return best_cost

def run():
	out = ''
	T = int(input())
	for i in range(T):
		N = int(stdin.readline())
		C = [int(x) for x in stdin.readline().split()]
		print(solve(N, C))
run()


def prob3(C, n):
	minCost = (C[0] + C[1]) * n
	oddMin = C[0]
	evenMin = C[1]
	(oddSum, evenSum) = (C[0], C[1])
	(oddCount, evenCount) = (1, 1)
	for i in range(2, len(C)):
		if i % 2 == 0:
			oddCount += 1
			oddSum += C[i]
			oddMin = min(oddMin, C[i])
			minCost = min(minCost, evenSum + (n - evenCount) * evenMin + (oddSum + (n - oddCount) * oddMin))
		else:
			evenCount += 1
			evenSum += C[i]
			evenMin = min(evenMin, C[i])
			minCost = min(minCost, evenSum + (n - evenCount) * evenMin + (oddSum + (n - oddCount) * oddMin))
	return minCost
t = int(input())
for t in range(t):
	n = int(input())
	C = [int(i) for i in input().split()][:n]
	print(prob3(C, n))


import math

def solve(m1, m2, c, n, dp1, dp2):
	ans = 0
	c1 = (max(m1, m2) + 1) // 2 - max(m1, m2) % 2
	c2 = (max(m1, m2) + 1) // 2 - 1
	ans += dp1[max(m1, m2)] - c[m1]
	ans += dp2[max(m1, m2)] - c[m2]
	ans += c[m1] * (n - c1)
	ans += c[m2] * (n - c2)
	return ans
t = int(input())
for k in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	min1 = 0
	min2 = 1
	dp1 = []
	sm1 = 0
	dp2 = []
	sm2 = 0
	for i in range(n):
		if i % 2 == 0:
			sm1 += c[i]
		else:
			sm2 += c[i]
		dp1.append(sm1)
		dp2.append(sm2)
	ans = n * (c[0] + c[1])
	for i in range(2, n):
		if c[i] < c[min1] and i % 2 == 0:
			min1 = i
		elif c[i] < c[min2] and i % 2 == 1:
			min2 = i
		ans = min(ans, solve(min1, min2, c, n, dp1, dp2))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	min1 = a[0]
	min2 = 1000000000.0
	ans = 1e+18
	sum = a[0]
	for i in range(1, n):
		sum = sum + a[i]
		if i % 2 == 1:
			min2 = min(min2, a[i])
		else:
			min1 = min(min1, a[i])
		res = sum - min1 - min2
		j = i - 1
		p = n - j // 2
		q = n - (j - j // 2)
		res = res + p * min2 + q * min1
		ans = min(ans, res)
	print(int(ans))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from heapq import heapify, heappush as hp, heappop as hpop
for t in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	ans = 10 ** 18
	h1 = []
	h2 = []
	heapify(h1)
	heapify(h2)
	(c1, c2) = (0, 0)
	hp(h1, c[0])
	c1 = c[0]
	for i in range(1, n):
		if i % 2:
			hp(h2, c[i])
			c2 += c[i]
		else:
			hp(h1, c[i])
			c1 += c[i]
		a = hpop(h1)
		b = hpop(h2)
		ans = min(ans, a * (n - len(h1)) + c1 - a + b * (n - len(h2)) + c2 - b)
		hp(h1, a)
		hp(h2, b)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	flag = True
	a = []
	b = []
	for i in l:
		if flag:
			a.append(i)
		else:
			b.append(i)
		flag = not flag
	x = len(a)
	y = len(b)
	z = max(x, y)
	la = lb = n
	ca = cb = 0
	ta = tb = 1000000000
	min_a = a[0]
	min_b = b[0]
	cost = []
	s_a = 0
	s_b = 0
	for i in range(n):
		if i % 2 == 0:
			j = i // 2
			s_a += a[j]
			min_a = min(min_a, a[j])
			temp = s_a + s_b + (n - j - 1) * min_a + (n - j) * min_b
			cost.append(temp)
		else:
			j = i // 2
			min_b = min(min_b, b[j])
			s_b += b[j]
			temp = s_a + s_b + (n - j - 1) * min_b + (n - j - 1) * min_a
			cost.append(temp)
	print(min(cost))


t = int(input())
for i in range(t):
	n = int(input())
	zoz = [int(j) for j in input().split()]
	ma = 10 ** 9 + 1
	mb = 10 ** 9 + 1
	cs = 0
	fin = []
	for j in range(n):
		if j % 2 == 0:
			if zoz[j] < ma:
				if ma != 10 ** 9 + 1:
					cs += ma
				ma = zoz[j]
			else:
				cs += zoz[j]
			if j >= 1:
				fin.append(cs + ma * (n - j // 2) + mb * (n - (j - 1) // 2))
		else:
			if zoz[j] < mb:
				if mb != 10 ** 9 + 1:
					cs += mb
				mb = zoz[j]
			else:
				cs += zoz[j]
			if j >= 1:
				fin.append(cs + ma * (n - j // 2) + mb * (n - (j - 1) // 2))
	print(min(fin))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	best = float('inf')
	mn = [float('inf')] * 2
	sm = [0] * 2
	for i in range(n):
		mn[i % 2] = min(mn[i % 2], arr[i])
		sm[i % 2] += arr[i]
		best = min(best, sum((sm[j] + mn[j] * (n - (i - j) // 2 - 1) for j in [0, 1])))
	print(best)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
from copy import deepcopy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()
for _ in range(inp()):
	n = inp()
	c = inpl()
	res = (c[0] + c[1]) * n
	O = c[1]
	E = c[0]
	ce = c[0:n:2]
	co = c[1:n:2]
	ce = list(itertools.accumulate(ce))
	co = list(itertools.accumulate(co))
	for i in range(2, n):
		if i % 2:
			O = min(O, c[i])
			ln = (i - 1) // 2
		else:
			E = min(E, c[i])
		eln = oln = i // 2
		if i % 2 == 0:
			oln -= 1
		ans = co[oln] - O + O * (n - oln) + ce[eln] - E + E * (n - eln)
		res = min(res, ans)
	print(res)


def inp():
	return int(input())
import math

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
import bisect
import heapq
test_cases = inp()

def solve(N, C):
	horizontal = []
	vertical = []
	horizontal.append(C[0])
	vertical.append(C[1])
	horizontal_sum = C[0]
	vertical_sum = C[1]
	smallest_horizontal = C[0]
	smallest_vertical = C[1]
	horizontal_cost = C[0] * N
	vertical_cost = C[1] * N
	total_cost = horizontal_cost + vertical_cost
	last_index_added = 1
	smallest_total_cost = total_cost
	while last_index_added < N - 1:
		last_index_added += 1
		if last_index_added % 2 == 0:
			horizontal.append(C[last_index_added])
			horizontal_sum += C[last_index_added]
			smallest_horizontal = min(smallest_horizontal, C[last_index_added])
			horizontal_cost = (horizontal_sum - smallest_horizontal) * 1 + (N - math.floor(last_index_added / 2)) * smallest_horizontal
			total_cost = horizontal_cost + vertical_cost
			smallest_total_cost = min(smallest_total_cost, total_cost)
		else:
			vertical.append(C[last_index_added])
			vertical_sum += C[last_index_added]
			smallest_vertical = min(smallest_vertical, C[last_index_added])
			vertical_cost = (vertical_sum - smallest_vertical) * 1 + (N - math.floor(last_index_added / 2)) * smallest_vertical
			total_cost = horizontal_cost + vertical_cost
			smallest_total_cost = min(smallest_total_cost, total_cost)
	print(smallest_total_cost)
for i in range(test_cases):
	N = inp()
	C = inlt()
	solve(N, C)


def answer():
	ans = 1e+50
	(m1, m2) = (1e+50, 1e+50)
	(v1, v2, c1, c2) = (0, 0, 0, 0)
	for i in range(n):
		if i & 1:
			m1 = min(m1, a[i])
			v1 += a[i]
			c1 += 1
		else:
			m2 = min(m2, a[i])
			v2 += a[i]
			c2 += 1
		ans = min(ans, v1 + v2 + m1 * (n - c1) + m2 * (n - c2))
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


import sys
input = iter(sys.stdin.read().splitlines()).__next__

def solve():
	n = int(input())
	c = list(map(int, input().split()))
	min_cost_right = c[0]
	min_cost_up = c[1]
	min_cost = min_cost_right * n + min_cost_up * n
	cost = min_cost
	for i in range(2, n):
		if i % 2:
			if c[i] < min_cost_up:
				cost -= min_cost_up * (n - i // 2)
				cost += c[i] * (n - i // 2)
				min_cost_up = c[i]
			else:
				cost += c[i] - min_cost_up
		elif c[i] < min_cost_right:
			cost -= min_cost_right * (n - i // 2)
			cost += c[i] * (n - i // 2)
			min_cost_right = c[i]
		else:
			cost += c[i] - min_cost_right
		min_cost = min(cost, min_cost)
	return min_cost
t = int(input())
output = []
for _ in range(t):
	output.append(solve())
print(*output, sep='\n')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	right = [i for i in arr[::2]]
	up = [i for i in arr[1::2]]
	(r, u) = (999999999999999999999999, 99999999999999999999999)
	(s1, s2) = (0, 0)
	total = 999999999999999999999999
	for i in range(len(right)):
		s1 += right[i]
		r = min(r, right[i])
		t1 = s1 + r * (n - i - 1)
		if i > len(up) - 1:
			break
		s2 += up[i]
		u = min(u, up[i])
		t2 = s2 + u * (n - i - 1)
		total = min(total, t1 + t2)
	(r, u) = (right[0], 9999999999999999999999)
	(s1, s2) = (right[0], 0)
	for i in range(1, len(right)):
		s1 += right[i]
		r = min(r, right[i])
		t1 = s1 + r * (n - i - 1)
		s2 += up[i - 1]
		u = min(u, up[i - 1])
		t2 = s2 + u * (n - i)
		total = min(total, t1 + t2)
	print(total)


def solve(c):
	m = min(c)
	k = len(c)
	return m * (n - k) + sum(c)
t = int(input())
ans = []
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	res = arr[0] * n + arr[1] * n
	curr = res
	(rmin, umin) = (arr[0], arr[1])
	for (i, v) in enumerate(arr[2:], start=2):
		if i % 2 == 0:
			k = i // 2 + 1
			if v < rmin:
				curr += (n - (k - 1)) * v - (n - (k - 1)) * rmin
				rmin = v
			else:
				curr += v - rmin
		else:
			k = (i + 1) // 2
			if v < umin:
				curr += (n - (k - 1)) * v - (n - (k - 1)) * umin
				umin = v
			else:
				curr += v - umin
		if curr < res:
			res = curr
	ans.append(res)
for i in ans:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	sum_right = c[0]
	sum_up = c[1]
	min_right = c[0]
	min_up = c[1]
	count_up = 1
	count_right = 1
	cost = sum_right + sum_up + min_up * (n - count_up) + min_right * (n - count_right)
	for k in range(2, n):
		if k % 2 == 0:
			min_right = min(min_right, c[k])
			sum_right += c[k]
			count_right += 1
		else:
			min_up = min(min_up, c[k]) if k % 2 == 1 else min_up
			sum_up += c[k]
			count_up += 1
		cost = min(cost, sum_right + sum_up + min_up * (n - count_up) + min_right * (n - count_right))
	print(cost)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lh = []
	lv = []
	for i in range(0, n, 2):
		lh.append(l[i])
	for i in range(1, n, 2):
		lv.append(l[i])
	minans = 10000000000
	minh = 100000000000
	minv = 100000000000
	sumh = 0
	sumv = 0
	count = 10 ** 16
	counth = 100000000000
	countv = 100000000000
	minv1 = 100000000000
	for i in range(len(lv)):
		minh = min(minh, lh[i])
		sumh += lh[i]
		counth = minh * (n - i - 1) + sumh
		minv1 = minv
		minv = min(minv, lv[i])
		sumv += lv[i]
		if i == 0:
			countv = minv * (n - i - 1) + sumv
		else:
			countv = min(minv * (n - i - 1) + sumv, minv1 * (n - i) + sumv - lv[i])
		count = min(count, counth + countv)
	if len(lh) != len(lv):
		count = min(count, sum(lh) + (n - len(lh)) * min(lh) + sum(lv) + (n - len(lv)) * min(lv))
	print(count)


from sys import stdin, stdout
input = stdin.readline
from collections import Counter
import bisect
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split(' ')))
	even = c[0::2]
	odd = c[1::2]
	evenMin = even[0]
	oddMin = odd[0]
	dE = [n * even[0]]
	dO = [n * odd[0]]
	for i in range(1, len(even)):
		if even[i] < evenMin:
			temp = (n - i) * evenMin
			dE.append(dE[i - 1] + (n - i) * even[i] - temp)
			evenMin = even[i]
		else:
			temp = evenMin
			dE.append(dE[i - 1] + even[i] - temp)
	for i in range(1, len(odd)):
		if odd[i] < oddMin:
			temp = (n - i) * oddMin
			dO.append(dO[i - 1] + (n - i) * odd[i] - temp)
			oddMin = odd[i]
		else:
			temp = oddMin
			dO.append(dO[i - 1] + odd[i] - temp)
	mn = dE[0] + dO[0]
	ans = dE[0] + dO[0]
	(j, k) = (0, 0)
	for i in range(2, n):
		if i % 2:
			ans = ans - dO[j] + dO[j + 1]
			j += 1
		else:
			ans = ans - dE[k] + dE[k + 1]
			k += 1
		if ans < mn:
			mn = ans
	print(mn)


def local_ans(n, count, _min, _sum):
	return (n - count + 1) * _min + (_sum - _min)

def solve(n, cc):
	min_ans = None
	_next = 2
	count1 = 1
	min1 = cc[0]
	sum1 = cc[0]
	count2 = 0
	min2 = cc[1]
	sum2 = 0
	for i in range(1, len(cc)):
		if _next == 2:
			count2 += 1
			min2 = min(min2, cc[i])
			sum2 += cc[i]
			_next = 1
		else:
			count1 += 1
			min1 = min(min1, cc[i])
			sum1 += cc[i]
			_next = 2
		new_ans = local_ans(n, count1, min1, sum1) + local_ans(n, count2, min2, sum2)
		if min_ans is None or min_ans > new_ans:
			min_ans = new_ans
	return min_ans

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		cc = [int(x) for x in input().split()]
		print(solve(n, cc))
main()


import sys

def solve(n, costs):
	pref = [costs[0]]
	for i in costs[1:]:
		pref.append(i + pref[-1])
	i0 = 0
	i1 = 0
	min0 = costs[0]
	min1 = costs[1]
	m = n * (min0 + min1)
	for i in range(2, n):
		if i & 1:
			i1 += 1
			min1 = min(min1, costs[i])
		else:
			i0 += 1
			min0 = min(min0, costs[i])
		newm = pref[i] - min0 - min1 + (n - i0) * min0 + (n - i1) * min1
		m = min(m, newm)
	return m
for _ in range(int(input())):
	n = int(input())
	cost = list(map(int, input().split()))
	print(solve(n, cost))


def solve(n, c):
	(king_hoz, king_vert) = (c[0], c[1])
	stair_sum = 0
	reach_sum = n * c[0] + n * c[1]
	m = stair_sum + reach_sum
	singles_sum = c[0] + c[1]
	hoz_singles = vert_singles = 1
	for i in range(2, n):
		singles_sum += c[i]
		cost = singles_sum
		if i % 2 == 0:
			if c[i] < king_hoz:
				king_hoz = c[i]
			hoz_singles += 1
		else:
			if c[i] < king_vert:
				king_vert = c[i]
			vert_singles += 1
		cost += king_hoz * (n - hoz_singles)
		cost += king_vert * (n - vert_singles)
		m = min(m, cost)
	return m

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		c = list(map(int, input().split()))
		print(solve(n, c))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	odds = []
	evens = []
	for i in range(n):
		if i % 2 == 0:
			evens.append(l[i])
		else:
			odds.append(l[i])
	for i in range(1, len(evens)):
		evens[i] += evens[i - 1]
	for i in range(1, len(odds)):
		odds[i] += odds[i - 1]
	ans = l[0] * n + l[1] * n
	min0 = l[0]
	min1 = l[1]
	for i in range(2, n):
		temp = 0
		if i % 2 == 0:
			if l[i] < min0:
				min0 = l[i]
			temp += evens[i // 2]
			temp += odds[i // 2 - 1]
			temp += min0 * (n - i // 2 - 1)
			temp += min1 * (n - i // 2 + 1 - 1)
		else:
			if l[i] < min1:
				min1 = l[i]
			temp += odds[i // 2]
			temp += evens[i // 2]
			temp += min1 * (n - i // 2 - 1)
			temp += min0 * (n - i // 2 - 1)
		ans = min(ans, temp)
	print(ans)


import sys
import os.path
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
depth = 1000005
mod = 1000000007
lim = mod * mod
sys.setrecursionlimit(depth)
from math import inf, ceil, sqrt
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	(mna, mnb) = (l[0], l[1])
	(cna, cnb) = (1, 1)
	(sma, smb) = (l[0], l[1])
	ans = n * mna + n * mnb
	for i in range(2, n):
		if i & 1:
			smb += l[i]
			cnb += 1
			mnb = min(mnb, l[i])
		else:
			sma += l[i]
			cna += 1
			mna = min(mna, l[i])
		ans = min(ans, sma + (n - cna) * mna + smb + (n - cnb) * mnb)
	print(ans)


from collections import deque
from queue import PriorityQueue
for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	step = [n, n]
	minm = [float('inf'), float('inf')]
	ans = float('inf')
	sum1 = 0
	for k in range(n):
		sum1 += ar[k]
		step[k % 2] -= 1
		minm[k % 2] = min(minm[k % 2], ar[k])
		ans = min(ans, step[0] * minm[0] + step[1] * minm[1] + sum1)
	print(ans)


n = int(input())
while n > 0:
	n -= 1
	num = int(input())
	arr = list(map(int, input().split()))
	lastH = arr[0]
	lastV = arr[1]
	minH = arr[0]
	minV = arr[1]
	counterV = 1
	counterH = 1
	ans = arr[0] * num + arr[1] * num
	for i in range(2, num):
		if i % 2 == 0:
			minH = min(minH, arr[i])
			counterH += 1
			lastH += arr[i]
		else:
			minV = min(minV, arr[i])
			counterV += 1
			lastV += arr[i]
		ans = min(ans, lastH + minH * (num - counterH) + lastV + minV * (num - counterV))
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f1 = [0] * n
	f2 = [0] * n
	f1[0] = l[0]
	f2[1] = l[1]
	m1 = [0] * n
	m2 = [0] * n
	m1[0] = l[0]
	m2[1] = l[1]
	for i in range(2, n):
		if i % 2 == 0:
			f1[i] = f1[i - 2] + l[i]
			m1[i] = min(l[i], m1[i - 2])
		else:
			f2[i] = f2[i - 2] + l[i]
			m2[i] = min(l[i], m2[i - 2])
	m = n * (l[0] + l[1])
	for i in range(2, n):
		if i % 2 == 0:
			a = i // 2 + 1
			b = i // 2
			temp = 0
			temp += f1[i] - m1[i]
			temp += (n - a + 1) * m1[i]
			if b != 1:
				temp += f2[i - 1] - m2[i - 1]
				temp += (n - b + 1) * m2[i - 1]
			else:
				temp += n * m2[i - 1]
		else:
			a = i // 2 + 1
			b = i // 2 + 1
			temp = 0
			temp += f2[i] - m2[i]
			temp += (n - b + 1) * m2[i]
			temp += f1[i - 1] - m1[i - 1]
			temp += (n - a + 1) * m1[i - 1]
		m = min(m, temp)
	print(m)


t = int(input())

def slv(n, a):
	(m0, m1) = (a[0], a[1])
	(s0, s1) = (a[0], a[1])
	(c0, c1) = (1, 1)
	ans = m0 * n + m1 * n
	for i in range(2, n):
		if i % 2 == 0:
			m0 = min(m0, a[i])
			c0 += 1
			s0 += a[i]
		else:
			m1 = min(m1, a[i])
			c1 += 1
			s1 += a[i]
		ans = min(s0 + s1 + m0 * (n - c0) + m1 * (n - c1), ans)
	return ans
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(slv(n, a))


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = [0] * n
	sumOdd = arr[0]
	minOdd = arr[0]
	sumEven = arr[1]
	minEven = arr[1]
	cntOdd = 1
	cntEven = 1
	ans[1] = sumOdd + minOdd * (n - cntOdd) + sumEven + minEven * (n - cntEven)
	for i in range(2, n):
		if i % 2 == 0:
			sumOdd += arr[i]
			if arr[i] < minOdd:
				minOdd = arr[i]
			cntOdd += 1
		else:
			sumEven += arr[i]
			if arr[i] < minEven:
				minEven = arr[i]
			cntEven += 1
		ans[i] = sumOdd + minOdd * (n - cntOdd) + sumEven + minEven * (n - cntEven)
	fin = float('inf')
	for i in range(1, n):
		if ans[i] < fin:
			fin = ans[i]
	print(fin)


import sys
import math
from math import factorial, inf, gcd
from heapq import *
from functools import *
from itertools import *
from collections import *
from typing import *
sys.setrecursionlimit(10 ** 5)
t = 1
t = int(input())
for ii in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	(v1, v2) = ([a[i] for i in range(0, n, 2)], [a[i] for i in range(1, n, 2)])
	(p1, p2) = (list(accumulate(v1)), list(accumulate(v2)))
	ans = v1[0] * n + v2[0] * n
	(m1, m2) = (v1[0], v2[0])
	for i in range(1, len(v1)):
		m1 = min(m1, v1[i])
		ans = min(ans, p1[i] + (n - i - 1) * m1 + p2[i - 1] + m2 * (n - i))
		if i < len(v2):
			m2 = min(m2, v2[i])
			ans = min(ans, p1[i] + (n - i - 1) * m1 + p2[i] + m2 * (n - i - 1))
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	a = arr[0]
	b = arr[1]
	ans = a * n + b * n
	s = 0
	for i in range(2, n):
		if i % 2 == 0:
			if a < arr[i]:
				s += arr[i]
			else:
				s += a
				a = arr[i]
			ans = min(ans, s + b * (n - (i - 1) // 2) + a * (n - i // 2))
		else:
			if b < arr[i]:
				s += arr[i]
			else:
				s += b
				b = arr[i]
			ans = min(ans, s + (b + a) * (n - i // 2))
	print(ans)


from itertools import permutations as perm
from fractions import Fraction
from collections import *
from sys import stdin
from bisect import *
from heapq import *
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
fi = []
(t,) = gil()
for _ in range(t):
	(n,) = gil()
	c = gil()
	(sme, smo) = (c[0], c[1])
	ans = (sme + smo) * n
	base = c[0] + c[1]
	for i in range(2, n):
		base += c[i]
		if i & 1:
			smo = min(smo, c[i])
		else:
			sme = min(sme, c[i])
		k = i + 1
		e = n - k // 2 - (k & 1)
		o = n - k // 2
		ans = min(ans, base + e * sme + o * smo)
	fi.append(str(ans))
print('\n'.join(fi))


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	m0 = a[0]
	m1 = a[1]
	(s0, s1) = (a[0], a[1])
	(m, s) = ([0] * n, [0] * n)
	(m[0], m[1]) = (m0, m1)
	(s[0], s[1]) = (s0, s1)
	for i in range(2, n):
		if i % 2:
			if a[i] < m1:
				m1 = a[i]
			m[i] = m1
		else:
			if a[i] < m0:
				m0 = a[i]
			m[i] = m0
		s[i] = s[i - 2] + a[i]
	cos = [0] * n
	for i in range(n):
		if i % 2:
			cos[i] = s[i] * 1 + m[i] * (n - (i + 1) // 2)
		else:
			cos[i] = s[i] * 1 + m[i] * (n - i // 2 - 1)
	p = cos[0] + cos[1]
	for i in range(n - 1):
		c = cos[i] + cos[i + 1]
		if c < p:
			p = c
	print(p)

def main():
	for ii in range(int(input())):
		solve()
main()


import os
import sys
from bisect import bisect_right
from collections import Counter, defaultdict
from heapq import *
from io import BytesIO, IOBase
from math import gcd, inf, sqrt, ceil

def lcm(a, b):
	return a * b // gcd(a, b)

def getFactorization(x):
	ret = list()
	while x != 1:
		ret.append(spf[x])
		x = x // spf[x]
	return ret

def printDivisors(n):
	i = 2
	z = [1, n]
	while i <= sqrt(n):
		if n % i == 0:
			if n / i == i:
				z.append(i)
			else:
				z.append(i)
				z.append(n // i)
		i = i + 1
	return z

def cheaker(a):
	j = 1
	p = False
	for i in a:
		if i != j:
			break
		j += 1
	q = len(a)
	for i in a[::-1]:
		if i != q:
			break
		q -= 1
	for i in range(j - 1, q):
		if a[i] == i + 1:
			return False
	return True

def create(n, x, f):
	pq = len(bin(n)[2:])
	if f == 0:
		tt = min
	else:
		tt = max
	dp = [[inf] * n for _ in range(pq)]
	dp[0] = x
	for i in range(1, pq):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = tt(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def enquiry(l, r, dp, f):
	if l > r:
		return inf if not f else -inf
	if f == 1:
		tt = max
	else:
		tt = min
	pq1 = len(bin(r - l + 1)[2:]) - 1
	return tt(dp[pq1][l], dp[pq1][r - (1 << pq1) + 1])

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	x = []
	for i in range(2, n + 1):
		if prime[i]:
			x.append(i)
	return x

def main():
	for _ in range(int(input())):
		n = int(input())
		a = [int(x) for x in input().split()]
		(x, y) = ([], [])
		for i in range(n):
			if i % 2 == 0:
				x.append(a[i])
			else:
				y.append(a[i])
		dp = [0] * len(x)
		dp[0] = x[0] * n
		m = x[0]
		s = x[0]
		for i in range(1, len(x)):
			m = min(x[i], m)
			s += x[i]
			dp[i] = s - m + (n - i) * m
		dp12 = [0] * len(y)
		dp12[0] = y[0] * n
		m = y[0]
		s = y[0]
		for i in range(1, len(y)):
			m = min(y[i], m)
			s += y[i]
			dp12[i] = s - m + (n - i) * m
		s = inf
		for i in range(min(len(x), len(y))):
			if len(x) > i + 1:
				s = min(s, dp[i + 1] + dp12[i])
			elif len(y) > i + 1:
				s = min(s, dp[i] + dp12[i + 1])
			s = min(s, dp[i] + dp12[i])
		print(s)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	cs = [int(c) for c in input().split()]
	sum_odds = 0
	min_odds = 1000000000
	num_odds = 0
	sum_evens = 0
	min_evens = 1000000000
	num_evens = 0
	ans = 1000000000000000.0
	for i in range(len(cs)):
		if i % 2 == 0:
			num_evens += 1
			sum_evens += cs[i]
			min_evens = min(min_evens, cs[i])
		else:
			num_odds += 1
			sum_odds += cs[i]
			min_odds = min(min_odds, cs[i])
		ans = min(ans, sum_evens + min_evens * (n - num_evens) + sum_odds + min_odds * (n - num_odds))
	print(int(ans))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = arr[0] * n + arr[1] * n
	mi0 = arr[0]
	mi1 = arr[1]
	ma0 = arr[0]
	ma1 = arr[1]
	dp = [count]
	mi0_count = n
	mi1_count = n
	for i in range(2, n):
		if i % 2 == 0:
			if arr[i] < mi0:
				count -= (mi0_count - 1) * mi0
				mi0_count -= 1
				mi0 = arr[i]
				count += mi0_count * mi0
			elif arr[i] >= mi0 and arr[i] < ma0:
				mi0_count -= 1
				count -= mi0
				count += arr[i]
			else:
				ma0 = arr[i]
				count -= mi0
				count += ma0
				mi0_count -= 1
		elif arr[i] <= mi1:
			count -= (mi1_count - 1) * mi1
			mi1_count -= 1
			mi1 = arr[i]
			count += mi1_count * mi1
		elif arr[i] > mi1 and arr[i] < ma1:
			mi1_count -= 1
			count -= mi1
			count += arr[i]
		else:
			ma1 = arr[i]
			count -= mi1
			count += ma1
			mi1_count -= 1
		dp.append(count)
	print(min(dp))


import sys
import math
input = sys.stdin.readline

class Problem:

	def __init__(self):
		pass

	def solve(self):
		t = int(input())
		for _ in range(t):
			n = int(input())
			C = list(map(int, input().split()))
			omin = emin = ans = int(pow(10, 20))
			osum = esum = 0
			for i in range(len(C)):
				pos = i + 1
				if pos % 2 == 0:
					esum += C[i]
					emin = min(emin, C[i])
				else:
					osum += C[i]
					omin = min(omin, C[i])
				oused = int((pos + 1) / 2)
				eused = int(pos / 2)
				C1 = osum - omin + (n - oused + 1) * omin
				C2 = esum - emin + (n - eused + 1) * emin
				ans = min(ans, C1 + C2)
			print(ans)

def main():
	p = Problem()
	p.solve()
main()


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))

def ans(ar, n):
	mi = ar[0]
	ix = 0
	pre = ar[0]
	bmi = ar[1]
	bix = 1
	bpre = ar[1]
	su = n * (ar[0] + ar[1])
	for i in range(2, n):
		if (i + 1) % 2:
			if mi > ar[i]:
				mi = ar[i]
				ix = i
			pre += ar[i]
			(ax, bx) = (i // 2 + 1, i // 2)
			su = min(su, mi * (n - ax) + pre + bmi * (n - bx) + bpre)
		else:
			if bmi > ar[i]:
				bmi = ar[i]
				bix = i
			bpre += ar[i]
			(ax, bx) = ((i + 1) // 2, (i + 1) // 2)
			su = min(su, mi * (n - ax) + pre + bmi * (n - bx) + bpre)
	return su
(t,) = I()
for _ in range(t):
	(n,) = I()
	ct = I()
	print(ans(ct, n))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def st():
	return input().rstrip('\n')

def lis():
	return list(map(int, input().split()))

def ma():
	return map(int, input().split())
t = inp()
while t:
	t -= 1
	n = inp()
	a = lis()
	res = n * a[0] + n * a[1]
	ans = res
	li = [[n * a[0], a[0], n], [n * a[1], a[1], n]]
	for i in range(2, n):
		x = li[0][:]
		li = [li[1]][:]
		if a[i] <= x[1]:
			if x[2] != 1:
				nres = res - x[0]
				nres += x[1]
				nres += (x[2] - 1) * a[i]
				ans = min(ans, nres)
				res = nres
				li.append([(x[2] - 1) * a[i], a[i], x[2] - 1])
		elif x[2] != 1:
			nres = res - x[0]
			nres += a[i]
			nres += (x[2] - 1) * x[1]
			ans = min(ans, nres)
			res = nres
			li.append([(x[2] - 1) * x[1], x[1], x[2] - 1])
	print(ans)


for i in range(int(input())):
	n = int(input())
	cost = list(map(int, input().split()))
	nx = n
	ny = n
	mx = float('inf')
	my = float('inf')
	s = 0
	ans = float('inf')
	for i in range(n):
		if i % 2 == 0:
			ny = ny - 1
			my = min(my, cost[i])
		else:
			nx = nx - 1
			mx = min(mx, cost[i])
		s = s + cost[i]
		ans = min(ans, s + my * ny + mx * nx)
	print(ans)


t = int(input())
INF = 10 ** 18
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	m = [INF, INF]
	s = [0, 0]
	cnt = [0, 0]
	ans = INF
	for i in range(n):
		m[i % 2] = min(c[i], m[i % 2])
		s[i % 2] += c[i]
		cnt[i % 2] += 1
		v = 0
		for i in range(2):
			v += m[i] * (n - cnt[i]) + s[i]
		ans = min(ans, v)
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	ans = 10 ** 200
	(hi, vi, hm, vm) = (0, 0, 10 ** 10, 10 ** 10)
	(x, y) = (0, 0)
	for i in range(n):
		if i % 2 == 0:
			if c[i] < hm:
				hm = c[i]
			hi += 1
			x = x + c[i]
		else:
			if c[i] < vm:
				vm = c[i]
			vi += 1
			y = y + c[i]
		ans = min(ans, x + y + (n - hi) * hm + (n - vi) * vm)
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	rmin = rtot = c[0]
	umin = utot = c[1]
	hprice = rmin * n
	uprice = umin * n
	ans = hprice + uprice
	for i in range(2, n):
		if i & 1:
			utot += c[i]
			umin = min(umin, c[i])
			uprice = utot + umin * (n - i // 2 - 1)
			ans = min(ans, hprice + uprice)
		else:
			rtot += c[i]
			rmin = min(rmin, c[i])
			hprice = rtot + rmin * (n - i // 2 - 1)
			ans = min(ans, hprice + uprice)
	print(ans)


import math
import heapq

def S():
	return input()

def M():
	return map(int, input().split())

def I():
	return int(S())

def L():
	return list(M())
for _ in range(I()):
	n = I()
	l = L()
	m1 = l[0]
	m2 = l[1]
	a = [(m1, m2), (m1, m2)]
	for i in range(2, n):
		if i % 2 == 0:
			if l[i] < m1:
				m1 = l[i]
		elif l[i] < m2:
			m2 = l[i]
		a.append((m1, m2))
	p = n * (l[0] + l[1])
	k = 0
	ar = []
	for i in range(n):
		k += l[i]
		ar.append(k)
	for i in range(2, n):
		(m1, m2) = a[i]
		e = i // 2 + 1
		o = i + 1 - e
		s = ar[i] - m1 - m2 + (n - e + 1) * m1 + (n - o + 1) * m2
		if s < p:
			p = s
	print(p)


def ints():
	return list(map(int, input().split()))

def case():
	(n,) = ints()
	c = ints()
	cx = c[::2]
	cy = c[1::2]
	cy.append(cy[-1])
	res = cx[0] * n + cy[0] * n
	mincx = cx[0]
	sumcx = cx[0]
	mincy = cy[0]
	sumcy = cy[0]
	for i in range(1, (n + 1) // 2):
		if cx[i] < mincx:
			mincx = cx[i]
		sumcx += cx[i]
		cost = sumcx + mincx * (n - i - 1) + sumcy + mincy * (n - i)
		if cost < res:
			res = cost
		if cy[i] < mincy:
			mincy = cy[i]
		sumcy += cy[i]
		cost = sumcx + mincx * (n - i - 1) + sumcy + mincy * (n - i - 1)
		if cost < res:
			res = cost
	return res
(t,) = ints()
for i in range(t):
	print(case())


import math
t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().split()))
	u = l[0]
	r = l[1]
	m1 = l[0]
	m2 = l[1]
	cost = l[0] * n + l[1] * n
	u1 = 1
	r1 = 1
	for i in range(2, n):
		if i % 2 == 0:
			m1 = min(m1, l[i])
			u = u + l[i]
			u1 = u1 + 1
		else:
			m2 = min(m2, l[i])
			r = r + l[i]
			r1 = r1 + 1
		cost = min(cost, u + (n - u1) * m1 + r + (n - r1) * m2)
	print(cost)
	t = t - 1


def min_cost(n: int, costs: list) -> int:
	ans = float('inf')
	(even, odd) = (0, 0)
	(even_cost, odd_cost) = (0, 0)
	(even_min, odd_min) = (float('inf'), float('inf'))
	for cost in costs:
		if even > odd:
			odd += 1
			odd_cost += cost
			odd_min = min(odd_min, cost)
		else:
			even += 1
			even_cost += cost
			even_min = min(even_min, cost)
		even_costs = even_cost + (n - even) * even_min
		odd_costs = odd_cost + (n - odd) * odd_min
		ans = min(ans, even_costs + odd_costs)
	return ans
for _ in range(int(input())):
	n = int(input())
	costs = [int(cost) for cost in input().split()]
	print(min_cost(n, costs))


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	d = [0] * n
	m = 10 ** 10
	s1 = [0]
	for i in range(0, n, 2):
		s1.append(s1[-1] + c[i])
		m = min(m, c[i])
		d[i] = s1[-1] + m * (n - len(s1) + 1)
	m = 10 ** 10
	s1 = [0]
	for i in range(1, n, 2):
		s1.append(s1[-1] + c[i])
		m = min(m, c[i])
		d[i] = s1[-1] + m * (n - len(s1) + 1)
	m = 10 ** 32
	for i in range(n - 1):
		m = min(m, d[i] + d[i + 1])
	print(m)


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
import heapq

def solve():
	n = ii()
	c = li()
	m = 10000000000000000000000
	pree = [0] * n
	preo = [0] * n
	mine = [0] * n
	mino = [0] * n
	mine[0] = c[0]
	pree[0] = c[0]
	for i in range(n - 1):
		if i >= 1:
			pree[i + 1] += pree[i - 1]
			mine[i + 1] = min(mine[i - 1], c[i + 1])
		else:
			mine[i + 1] = c[i + 1]
		pree[i + 1] += c[i + 1]
		ans = mine[i] * (n - i // 2) + pree[i] - mine[i]
		ans += mine[i + 1] * (n - (i + 1) // 2) + pree[i + 1] - mine[i + 1]
		m = min(m, ans)
	print(m)
t = 1
t = int(input())
for _ in range(t):
	solve()


T = int(input())
for t in range(T):
	n = int(input())
	cs = [int(x) for x in input().split()]
	bests = [cs[0], cs[1]]
	totals = [cs[0], cs[1]]
	ans = 12345677890123409875678
	for i in range(2, n + 1):
		firsts = i - i // 2 - 1
		seconds = i // 2 - 1
		cost = bests[0] * (n - firsts) + (totals[0] - bests[0]) + bests[1] * (n - seconds) + (totals[1] - bests[1])
		ans = min(ans, cost)
		if i < n:
			index = i % 2
			bests[index] = min(bests[index], cs[i])
			totals[index] += cs[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	s = [c[0], c[1]]
	x = [c[0], c[1]]
	salida = sum(x) * n
	for j in range(2, n):
		I = j % 2
		s[I] = s[I] + c[j]
		x[I] = min(x[I], c[j])
		sm = sum(s) + x[0] * (n - j // 2 - 1) + x[1] * (n - (j + 1) // 2)
		salida = min(salida, sm)
	print(salida)


import os
import sys
from io import BytesIO, IOBase
import threading
from bisect import bisect_right
from math import gcd, log
from collections import Counter
from pprint import pprint
from itertools import permutations
from bisect import bisect_right

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	smod = 0
	smev = 0
	smallod = float('inf')
	smallev = float('inf')
	ans = float('inf')
	for i in range(n):
		if i % 2 == 1:
			smod += arr[i]
			smallod = min(smallod, arr[i])
		else:
			smev += arr[i]
			smallev = min(smallev, arr[i])
		odc = smallod * (n - (i + 1) // 2) + smod
		evc = smallev * (n - (i + 2) // 2) + smev
		ans = min(ans, odc + evc)
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
for _ in range(int(input())):
	main()


import sys
from collections import defaultdict
input = sys.stdin.readline

def solve():
	n = int(input())
	costs = [int(x) for x in input().split()]
	minCost = float('inf')
	hSum = vSum = 0
	vMin = costs[0]
	hMin = costs[1]
	vSum += costs[0]
	h = 0
	v = 1
	prevCost = costs[0] * n
	for i in range(1, n):
		if i % 2 == 0:
			vSum += costs[i]
			v += 1
			vMin = min(vMin, costs[i])
			vCost = vSum + (n - v) * vMin
			minCost = min(minCost, prevCost + vCost)
			prevCost = vCost
		else:
			hSum += costs[i]
			h += 1
			hMin = min(hMin, costs[i])
			hCost = hSum + (n - h) * hMin
			minCost = min(minCost, prevCost + hCost)
			prevCost = hCost
	print(minCost)
t = int(input())
for _ in range(t):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	C = list(map(int, input().split()))
	A = []
	B = []
	for i in range(n):
		if i % 2 == 0:
			A.append(C[i])
		else:
			B.append(C[i])
	MINA = 1 << 60
	SUMA = 0
	ANSA = []
	for i in range(len(A)):
		x = A[i]
		SUMA += x
		MINA = min(MINA, x)
		ANSA.append(SUMA - MINA + MINA * (n - i))
	MINB = 1 << 60
	SUMB = 0
	ANSB = []
	for i in range(len(B)):
		x = B[i]
		SUMB += x
		MINB = min(MINB, x)
		ANSB.append(SUMB - MINB + MINB * (n - i))
	ANS = 1 << 60
	for i in range(len(ANSA)):
		for j in [i - 1, i]:
			if 0 <= j < len(ANSB):
				ANS = min(ANS, ANSA[i] + ANSB[j])
	print(ANS)


tc = int(input())
for t in range(tc):
	n = int(input())
	path = [int(x) for x in input().split()]
	even = True
	curBest = n * path[0] + n * path[1]
	minEven = path[0]
	minOdd = path[1]
	curEvenSum = path[0]
	curOddSum = path[1]
	cntEven = 1
	cntOdd = 1
	for i in path[2:]:
		if even:
			cntEven += 1
			curEvenSum += i
			if i < minEven:
				minEven = i
		else:
			cntOdd += 1
			curOddSum += i
			if i < minOdd:
				minOdd = i
		s = curEvenSum + (n - cntEven) * minEven + curOddSum + (n - cntOdd) * minOdd
		curBest = min(curBest, s)
		even = not even
	print(curBest)


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	emin = float('inf')
	omin = float('inf')
	ans = float('inf')
	temp = 0
	od = n
	ev = n
	for i in range(n):
		if i % 2 == 0:
			val = temp + od * arr[i] + ev * emin
			ans = min(ans, val)
			od -= 1
			omin = min(omin, arr[i])
			temp += arr[i]
		else:
			val = temp + ev * arr[i] + od * omin
			ans = min(ans, val)
			ev -= 1
			emin = min(emin, arr[i])
			temp += arr[i]
	print(ans)


from sys import stdin, stderr
input = stdin.readline

def dbp(*args, **kwargs):
	print(*args, file=stderr, **kwargs)

def get_int_list():
	return [int(x) for x in input().strip().split()]

def do_thing():
	n = int(input())
	clist = get_int_list()
	mincost = float('inf')
	mineven = clist[0]
	minodd = float('inf')
	evensum = clist[0]
	oddsum = 0
	evenc = 1
	oddc = 0
	for i in range(1, n):
		if i % 2 == 1:
			minodd = min(minodd, clist[i])
			oddc += 1
			oddsum += clist[i]
		else:
			mineven = min(mineven, clist[i])
			evenc += 1
			evensum += clist[i]
		cost = oddsum + evensum + ((n - evenc) * mineven + (n - oddc) * minodd)
		mincost = min(cost, mincost)
	return mincost

def multicase():
	maxcc = int(input().strip())
	for cc in range(maxcc):
		print(do_thing())
multicase()


import sys
from math import *
import threading
from itertools import count
from pprint import pprint
from collections import defaultdict
from heapq import heapify, heappop, heappush
sys.setrecursionlimit(300000)
mod = 10 ** 9 + 7
inf = 10 ** 15
decision = ['NO', 'YES']
yes = 'YES'
no = 'NO'
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def npr(n, r):
	return factorial(n) // factorial(n - r) if n >= r else 0

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(n - r)) if n >= r else 0

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val):
	ans = -1
	lb = 0
	ub = len(li) - 1
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = mid
			break
	return ans

def kadane(x):
	sum_so_far = 0
	current_sum = 0
	for i in x:
		current_sum += i
		if current_sum < 0:
			current_sum = 0
		else:
			sum_so_far = max(sum_so_far, current_sum)
	return sum_so_far

def pref(li):
	pref_sum = [0]
	for i in li:
		pref_sum.append(pref_sum[-1] + i)
	return pref_sum

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	li = []
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, len(prime)):
		if prime[p]:
			li.append(p)
	return li

def primefactors(n):
	factors = []
	while n % 2 == 0:
		factors.append(2)
		n //= 2
	for i in range(3, int(sqrt(n)) + 1, 2):
		while n % i == 0:
			factors.append(i)
			n //= i
	if n > 2:
		factors.append(n)
	return factors

def prod(li):
	ans = 1
	for i in li:
		ans *= i
	return ans
for _ in range(int(input()) if True else 1):
	n = int(input())
	a = list(map(int, input().split()))
	(cntu, cntr) = (0, 0)
	(prefu, prefr) = (0, 0)
	(xstep, ystep) = (n * a[1], n * a[0])
	ans = n * (a[0] + a[1])
	(mini_u, mini_r) = (a[0], a[1])
	for i in range(2, n):
		if i & 1 == 0:
			cntu += 1
			if mini_u < a[i]:
				prefu += a[i]
			else:
				prefu += mini_u
				mini_u = a[i]
			ystep = prefu + (n - cntu) * mini_u
		else:
			cntr += 1
			if mini_r < a[i]:
				prefr += a[i]
			else:
				prefr += mini_r
				mini_r = a[i]
			xstep = prefr + (n - cntr) * mini_r
		ans = min(ans, xstep + ystep)
	print(ans)


t = int(input())
for tt in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	s = [c[0], c[1]]
	x = [c[0], c[1]]
	ans = sum(x) * n
	for i in range(2, n):
		I = i % 2
		s[I] += c[i]
		x[I] = min(x[I], c[i])
		ss = sum(s) + x[0] * (n - i // 2 - 1) + x[1] * (n - (i + 1) // 2)
		ans = min(ans, ss)
	print(ans)
num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()


import math

def g(n, arr):
	summ1 = 0
	summ2 = 0
	prefixsumm = [0] * len(arr)
	for i in range(0, len(arr)):
		if i % 2 == 0:
			summ1 += arr[i]
			prefixsumm[i] = summ1
		else:
			summ2 += arr[i]
			prefixsumm[i] = summ2
	result = math.inf
	mineven = math.inf
	minodd = math.inf
	for i in range(0, len(prefixsumm) - 1):
		if i % 2 == 0:
			if arr[i] < mineven:
				mineven = arr[i]
			if arr[i + 1] < minodd:
				minodd = arr[i + 1]
			counteven = (i + 2) // 2
			countodd = counteven
			cal = prefixsumm[i] + (n - counteven) * mineven + prefixsumm[i + 1] + (n - countodd) * minodd
			if result > cal:
				result = cal
		else:
			if arr[i + 1] < mineven:
				mineven = arr[i + 1]
			if arr[i] < minodd:
				minodd = arr[i]
			counteven = (i + 3) // 2
			countodd = counteven - 1
			cal = prefixsumm[i] + (n - countodd) * minodd + prefixsumm[i + 1] + (n - counteven) * mineven
			if result > cal:
				result = cal
	print(result)
t = int(input())
for i in range(0, t):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	g(n, arr)


import math
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict

def arr_input():
	return list(map(int, input().split()))

def mul_input():
	return map(int, input().split())

def int_inp():
	return int(input())

def solution():
	n = int(input())
	c = list(map(int, input().split()))
	sa = c[0]
	sb = 0
	ma = c[0]
	mb = math.inf
	ca = 1
	cb = 0
	s = math.inf
	for i in range(1, n):
		if i % 2:
			cb += 1
			mb = min(c[i], mb)
			sb += c[i]
		else:
			ca += 1
			ma = min(c[i], ma)
			sa += c[i]
		s = min(s, sa + sb + (n - ca) * ma + (n - cb) * mb)
	print(s)
	return

def main():
	testcases = 1
	testcases = int(input())
	for _ in range(testcases):
		solution()
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
main()


def main():
	for ii in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		odd_sum = a[1]
		even_sum = a[0]
		(xo, xe) = (a[1], a[0])
		c = xo * n + xe * n
		for i in range(2, n):
			if i % 2:
				odd_sum += a[i]
				xo = min(a[i], xo)
			else:
				even_sum += a[i]
				xe = min(xe, a[i])
			cost = odd_sum + xo * (n - (i + 1) // 2) + even_sum + xe * (n - i // 2 - 1)
			c = min(c, cost)
		print(c)
main()


def calc():
	n = int(input())
	c = list(map(int, input().split(' ')))
	hor_sum = c[0]
	hor_min = c[0]
	ver_sum = c[1]
	ver_min = c[1]
	hors = 1
	vers = 1
	min_cost = n * c[0] + n * c[1]
	for i in range(2, n):
		if i % 2 == 0:
			hors += 1
			hor_sum += c[i]
			hor_min = min([hor_min, c[i]])
		else:
			vers += 1
			ver_sum += c[i]
			ver_min = min([ver_min, c[i]])
		hor_cost = (n - hors) * hor_min + hor_sum
		ver_cost = (n - vers) * ver_min + ver_sum
		min_cost = min([min_cost, hor_cost + ver_cost])
	print(min_cost)
t = int(input())
for j in range(t):
	calc()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	c1 = [c[i] for i in range(0, n, 2)]
	c2 = [c[i] for i in range(1, n, 2)]
	pref1 = [0]
	pref2 = [0]
	for i in range(len(c1)):
		pref1.append(c1[i] + pref1[i])
	for i in range(len(c2)):
		pref2.append(c2[i] + pref2[i])
	l1 = []
	l2 = []
	mn_1 = float('inf')
	mn_2 = float('inf')
	for i in range(len(c1)):
		mn_1 = min(mn_1, c1[i])
		l1.append(pref1[i + 1] + (n - i - 1) * mn_1)
	for i in range(len(c2)):
		mn_2 = min(mn_2, c2[i])
		l2.append(pref2[i + 1] + (n - i - 1) * mn_2)
	ans = l1[0] + l2[0]
	for i in range(1, len(c2)):
		ans = min(ans, l1[i] + l2[i], l1[i] + l2[i - 1])
	ans = min(ans, l1[-1] + l2[-1])
	print(ans)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]

def solve(N, C):
	C1 = [C[i] for i in range(0, N, 2)]
	C2 = [C[i] for i in range(1, N, 2)]
	M = N // 2
	m1 = C1[0]
	m2 = C2[0]
	asum1 = C1[0]
	asum2 = C2[0]
	score1 = C1[0] * N
	score2 = C2[0] * N
	score_min = score1 + score2
	for i in range(1, len(C1)):
		m1 = min(m1, C1[i])
		asum1 += C1[i]
		score1 = asum1 + m1 * (N - i - 1)
		score_min = min(score_min, score1 + score2)
		if i < len(C2):
			m2 = min(m2, C2[i])
			asum2 += C2[i]
			score2 = asum2 + m2 * (N - i - 1)
			score_min = min(score_min, score1 + score2)
	return score_min

def main():
	T0 = int(input())
	for _ in range(T0):
		N = int(input())
		C = list(map(int, input().split()))
		ans = solve(N, C)
		print(ans)
main()


T = int(input())
for _ in range(T):
	N = int(input())
	c = list(map(int, input().split()))
	(up, right) = (c[0], 0)
	(mup, mright) = (c[0], 2000000000.0)
	(cup, cright) = (1, 0)
	M = 9e+18
	for i in range(1, N):
		if i & 1:
			right += c[i]
			cright += 1
			mright = min(mright, c[i])
		else:
			up += c[i]
			cup += 1
			mup = min(mup, c[i])
		S = up + right
		S += mup * (N - cup)
		S += mright * (N - cright)
		M = min(M, S)
	print(M)


T = int(input())
r = 1
while r <= T:
	n = int(input())
	arr = list(map(int, input().split()))
	(minh, minv) = (arr[0], arr[1])
	tot = (minh + minv) * n
	ans = tot
	for i in range(2, n):
		if i % 2 == 0:
			if arr[i] < minh:
				tot -= (n - i // 2) * (minh - arr[i])
				minh = arr[i]
			else:
				tot += arr[i] - minh
		elif arr[i] < minv:
			tot -= (n - i // 2) * (minv - arr[i])
			minv = arr[i]
		else:
			tot += arr[i] - minv
		ans = min(ans, tot)
	print(ans)
	r += 1


t = int(input())
for tt in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	s = [c[0], c[1]]
	x = [c[0], c[1]]
	ans = sum(x) * n
	for i in range(2, n):
		I = i % 2
		s[I] += c[i]
		x[I] = min(x[I], c[i])
		ss = sum(s) + x[0] * (n - i // 2 - 1) + x[1] * (n - (i + 1) // 2)
		ans = min(ans, ss)
	print(ans)


from queue import Queue
from itertools import accumulate
from io import BytesIO, IOBase
from itertools import combinations
import threading
from collections import deque
from functools import reduce, cmp_to_key
import sys
from math import sqrt
import heapq
import random
import math
from collections import defaultdict
from collections import Counter
import io
import os
import bisect
from fractions import Fraction

def input():
	return sys.stdin.readline().strip()

def iinput():
	return int(input())

def tinput():
	return input().split()

def rinput():
	return map(int, tinput())

def rlinput():
	return list(rinput())
mod = int(1000000000.0) + 7

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def swap(arr, a, b):
	(arr[a], arr[b]) = (arr[b], arr[a])
t = 1
t = iinput()
for _ in range(t):
	n = iinput()
	C = rlinput()
	hormin = C[0]
	vertmin = C[1]
	horsum = C[0]
	versum = C[1]
	ans = n * horsum + n * versum
	for i in range(2, n):
		if i % 2:
			vertmin = min(vertmin, C[i])
			versum += C[i]
		else:
			hormin = min(hormin, C[i])
			horsum += C[i]
		ans = min(ans, horsum + versum + hormin * (n - i // 2 - 1) + vertmin * (n - (i + 1) // 2))
	print(ans)


list1 = []
for i in range(int(input())):
	n = int(input())
	s = list(map(lambda x: int(x), input().split()))
	price = n * s[0] + n * s[1]
	(min_1, min_2) = (s[0], s[1])
	k = n - 1
	price1 = price
	for j in range(2, n):
		if j % 2 == 0:
			price1 = price1 + s[j] - min_1
			if s[j] < min_1:
				price1 -= (k - 1) * (min_1 - s[j])
				min_1 = s[j]
		else:
			price1 += s[j] - min_2
			k -= 1
			if s[j] < min_2:
				price1 -= k * (min_2 - s[j])
				min_2 = s[j]
		if price1 < price:
			price = price1
	list1.append(price)
print(*list1, sep='\n')


import sys
import heapq
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
input = sys.stdin.readline
T = int(input())
while T:
	T -= 1
	n = int(input())
	a = list(map(int, input().split()))
	(minUp, minRight) = (a[0], a[1])
	(sumup, sumright) = (a[0], a[1])
	ans = (a[0] + a[1]) * n
	(elup, elright) = (1, 1)
	for i in range(2, n):
		(horcost, vertcost) = (0, 0)
		if i & 1:
			minRight = min(minRight, a[i])
			sumright += a[i]
			elright += 1
			horcost = sumright + (n - elright) * minRight
			vertcost = sumup + (n - elup) * minUp
		else:
			minUp = min(minUp, a[i])
			sumup += a[i]
			elup += 1
			horcost = sumright + (n - elright) * minRight
			vertcost = sumup + (n - elup) * minUp
		ans = min(ans, horcost + vertcost)
	print(ans)


from collections import deque, defaultdict
from math import sqrt, ceil, factorial, floor, inf, log2, sqrt
import bisect
import copy
from itertools import combinations
import sys

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = get_array()
	min_arr = [[inf for i in range(2)] for j in range(n)]
	sum_arr = [[0 for i in range(2)] for j in range(n)]
	(min_arr[0][0], sum_arr[0][0]) = (a[0], a[0])
	(min_arr[1][0], sum_arr[1][0]) = (a[0], a[0])
	(min_arr[1][1], sum_arr[1][1]) = (a[1], a[1])
	for i in range(2, n):
		min_arr[i][i % 2] = min(min_arr[i - 2][i % 2], a[i])
		min_arr[i][(i + 1) % 2] = min_arr[i - 1][(i + 1) % 2]
		sum_arr[i][i % 2] = sum_arr[i - 2][i % 2] + a[i]
		sum_arr[i][(i + 1) % 2] = sum_arr[i - 1][(i + 1) % 2]
	mini = inf
	for i in range(1, n):
		q = i + 1
		if q % 2 == 0:
			p = q // 2
			mini = min(mini, (min_arr[i][0] + min_arr[i][1]) * (n - p + 1) + sum_arr[i][0] + sum_arr[i][1] - min_arr[i][0] - min_arr[i][1])
		else:
			p = q // 2
			sumi = sum_arr[i][0] + sum_arr[i][1] - min_arr[i][0] - min_arr[i][1]
			mini1 = min(mini, min_arr[i][0] * (n - p) + min_arr[i][1] * (n - p + 1) + sumi)
			mini = min(mini, mini1)
	print(mini)


def find():
	n = int(input())
	mas = list(map(int, input().split()))
	min1 = mas[0]
	min2 = mas[1]
	ans1 = mas[0] * n
	ans2 = mas[1] * n
	res = ans1 + ans2
	s1 = mas[0]
	s2 = mas[1]
	j1 = j2 = 1
	for j in range(2, len(mas)):
		if j % 2 == 0:
			s1 += mas[j]
			min1 = min(min1, mas[j])
			ans1 = s1 - min1 + min1 * (n - j1)
			j1 += 1
		else:
			s2 += mas[j]
			min2 = min(min2, mas[j])
			ans2 = s2 - min2 + min2 * (n - j2)
			j2 += 1
		res = min(res, ans1 + ans2)
	print(res)
for i in range(int(input())):
	find()


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	n = ip()
	arr = list(inp())
	cur1 = 0
	cur2 = 0
	x1 = float('inf')
	x2 = float('inf')
	mincur1 = float('inf')
	mincur2 = float('inf')
	ans = float('inf')
	for i in range(n):
		if i & 1 == 0:
			mincur1 = min(arr[i], mincur1)
			x1 = cur1 + mincur1 * (n - i // 2 - 1) + arr[i]
			cur1 += arr[i]
		else:
			mincur2 = min(arr[i], mincur2)
			x2 = cur2 + mincur2 * (n - i // 2 - 1) + arr[i]
			cur2 += arr[i]
		ans = min(ans, x1 + x2)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	c = [int(x) for x in input().split()]
	(prices, mn_e, mn_o, s) = ([], c[0], c[1], c[0])
	for i in range(2, n + 1):
		s += c[i - 1]
		if i == n:
			pass
		elif i % 2 == 0:
			mn_e = min(mn_e, c[i])
		else:
			mn_o = min(mn_o, c[i])
		price = s + (n - (i + 1) // 2) * mn_e + (n - i // 2) * mn_o
		prices.append(price)
	print(min(prices))


import sys
from math import inf
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, sys.stdin.readline().split()))
	vert = []
	hori = []
	for i in range(n):
		if i % 2 == 0:
			vert.append(arr[i])
		else:
			hori.append(arr[i])
	vert_sum = [0 for _ in range((n + 1) // 2)]
	hori_sum = [0 for _ in range(n // 2)]
	now = n - 1
	now_sum = 0
	mini = inf
	for i in range((n + 1) // 2):
		if vert[i] < mini:
			mini = vert[i]
		now_sum += vert[i]
		vert_sum[i] = now_sum + mini * now
		now -= 1
	now = n - 1
	now_sum = 0
	mini = inf
	for i in range(n // 2):
		if hori[i] < mini:
			mini = hori[i]
		now_sum += hori[i]
		hori_sum[i] = now_sum + mini * now
		now -= 1
	dp = [0 for i in range(n - 1)]
	dp[0] = hori_sum[0] + vert_sum[0]
	for i in range(1, n - 1):
		dp[i] = vert_sum[(i + 1) // 2] + hori_sum[i // 2]
	print(min(dp))


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	mv1 = A[0]
	mv2 = A[1]
	(v1, v2) = (n, n)
	ans = v1 * mv1 + v2 * mv2
	ans1 = 0
	for i in range(2, n):
		if i % 2 == 0:
			if A[i] < mv1:
				ans1 = ans1 + mv1
				mv1 = A[i]
			else:
				ans1 = ans1 + A[i]
			v1 -= 1
			ans = min(ans, ans1 + v1 * mv1 + v2 * mv2)
		else:
			if A[i] < mv2:
				ans1 = ans1 + mv2
				mv2 = A[i]
			else:
				ans1 = ans1 + A[i]
			v2 -= 1
			ans = min(ans, ans1 + v1 * mv1 + v2 * mv2)
	print(ans)


from math import *
from collections import defaultdict as dt
from sys import stdin
inp = lambda : stdin.readline().strip()
I = lambda : int(inp())
M = lambda : map(int, stdin.readline().split())
L = lambda : list(map(int, stdin.readline().split()))
mod = 1000000009
inf = 100000000000000000000
ss = 'abcdefghijklmnopqrstuvwxyz'

def solve():
	n = I()
	l = L()
	(a, b, d, f) = ([], [], [], [])
	c = inf
	for i in range(n):
		if i % 2 == 0:
			a.append(l[i])
		else:
			b.append(l[i])
	x = len(a)
	y = len(b)
	e = 0
	for i in range(x):
		c = min(a[i], c)
		e = e + a[i]
		d.append(c * (n - i - 1) + e)
	c = inf
	e = 0
	for i in range(y):
		c = min(b[i], c)
		e = e + b[i]
		f.append(c * (n - i - 1) + e)
	c = inf
	(i, j) = (0, 0)
	while i < x - 1 and j < y:
		c = min(d[i] + f[j], c, d[i + 1] + f[j])
		i = i + 1
		j = j + 1
	print(min(c, d[-1] + f[-1]))
tt = 1
tt = I()
for _ in range(tt):
	solve()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m1 = a[0]
	m2 = a[1]
	s1 = a[0]
	s2 = 0
	z1 = 1
	z2 = 0
	min_cost = m1 * n + m2 * n
	for i in range(1, n):
		if i % 2 == 1:
			if a[i] < m2:
				m2 = a[i]
				cost = s1 + (n - z1) * m1 + s2 + (n - z2) * m2
				if cost < min_cost:
					min_cost = cost
			s2 += a[i]
			z2 += 1
		if i % 2 == 0:
			if a[i] < m1:
				m1 = a[i]
				cost = s1 + (n - z1) * m1 + s2 + (n - z2) * m2
				if cost < min_cost:
					min_cost = cost
			s1 += a[i]
			z1 += 1
	print(min_cost)


from sys import stdin
input = stdin.readline
T = int(input())
for _ in range(T):
	n = int(input())
	segs = list(map(int, input().split()))
	row = float('inf')
	col = segs[0]
	base_row = 0
	base_col = segs[0]
	res_row = 0
	res_col = segs[0] * n
	res = float('inf')
	for i in range(1, len(segs)):
		if i % 2:
			base_row += segs[i]
			if segs[i] < row:
				row = segs[i]
			res_row = base_row + row * (n - i // 2 - 1)
		else:
			base_col += segs[i]
			if segs[i] < col:
				col = segs[i]
			res_col = base_col + col * (n - i // 2 - 1)
		semi_res = res_row + res_col
		if res > semi_res:
			res = semi_res
	print(res)


T = int(input())
for t in range(1, T + 1):
	N = int(input())
	C = list(map(int, input().split()))
	min_cost = 2 ** 100
	(sum_even, sum_odd) = (0, C[0])
	(min_even, min_odd) = (2 ** 100, C[0])
	(even, odd) = (0, 1)
	for (i, c) in enumerate(C[1:]):
		if i % 2 == 0:
			sum_even += c
			min_even = min(min_even, c)
			even += 1
		else:
			sum_odd += c
			min_odd = min(min_odd, c)
			odd += 1
		cost = sum_even + min_even * (N - even) + sum_odd + min_odd * (N - odd)
		min_cost = min(min_cost, cost)
	print(min_cost)


t = int(input())
for _ in range(t):
	n = int(input())
	m = n
	costs = [int(i) for i in input().split()]
	(horizontal, vertical, ch_old, cv_old) = (0, 0, 0, 0)
	gesamt = sum(costs) * n
	(var, var2) = (True, False)
	min_ch = max(costs)
	min_cv = min_ch
	for c in costs:
		if var:
			if c < min_ch:
				min_ch = c
				horizontal = ch_old + c * n
			else:
				horizontal = ch_old + c + min_ch * (n - 1)
			var = False
			n -= 1
			ch_old += c
		else:
			if c < min_cv:
				min_cv = c
				vertical = cv_old + c * m
			else:
				vertical = cv_old + c + min_cv * (m - 1)
			(var, var2) = (True, True)
			m -= 1
			cv_old += c
			if c < min_cv:
				min_cv = c
		g = vertical + horizontal
		if g < gesamt and var2:
			gesamt = g
	print(gesamt)


quist = int(input())
for count in range(quist):
	m = int(input())
	c = list(map(int, input().split()))
	c1 = []
	c2 = []
	w = 0
	for i in c:
		if w == 0:
			c1.append(i)
			w = 1
		else:
			c2.append(i)
			w = 0
	n1 = 0
	s1 = 0
	m1 = -1
	d1 = -1
	p1 = []
	for i in c1:
		n1 += 1
		s1 += i
		if m1 != -1:
			m1 = min(m1, i)
		else:
			m1 = i
		d1 = s1 + m1 * (m - n1)
		p1.append(d1)
	n2 = 0
	s2 = 0
	m2 = -1
	d2 = -1
	p2 = []
	for i in c2:
		n2 += 1
		s2 += i
		if m2 != -1:
			m2 = min(m2, i)
		else:
			m2 = i
		d2 = s2 + m2 * (m - n2)
		p2.append(d2)
	x = -1
	i = 0
	while i < len(p1) and i < len(p2):
		if x == -1:
			x = p1[i] + p2[i]
		else:
			x = min(x, p1[i] + p2[i])
		i += 1
	i = 0
	while i + 1 < len(p1) and i < len(p2):
		if x == -1:
			x = p1[i + 1] + p2[i]
		else:
			x = min(x, p1[i + 1] + p2[i])
		i += 1
	print(x)


def a():
	t = int(input())
	o = []
	for i in range(t):
		n = int(input())
		c = list(map(int, input().split()))
		x = [c[0]]
		y = [c[1]]
		mx = c[0]
		my = c[1]
		sx = c[0]
		sy = c[1]
		r = c[0] * n + c[1] * n
		for j in range(2, n):
			if j % 2 == 0:
				x.append(c[j])
				sx += c[j]
				mx = min(mx, c[j])
			else:
				y.append(c[j])
				sy += c[j]
				my = min(my, c[j])
			temp = sx + (n - len(x)) * mx
			temp += sy + (n - len(y)) * my
			r = min(r, temp)
		o.append(r)
	for i in o:
		print(i)
a()


for x in range(int(input())):
	n = int(input())
	arr = list(map(int, input().strip().split()))
	a = [arr[0]]
	b = [arr[1]]
	amin = arr[0]
	bmin = arr[1]
	asum = arr[0]
	bsum = arr[1]
	alen = 1
	blen = 1
	help = bmin * (n - blen) + bsum + amin * (n - alen) + asum
	for i in range(2, n):
		val = arr[i]
		if i % 2 == 1:
			b.append(val)
			bmin = min(bmin, val)
			bsum += val
			blen += 1
		else:
			a.append(val)
			amin = min(val, amin)
			asum += val
			alen += 1
		help = min(help, bmin * (n - blen) + bsum + amin * (n - alen) + asum)
	print(help)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 10 ** 18
	som = 0
	cnt1 = 0
	cnt2 = 0
	x = 10 ** 18
	y = 10 ** 18
	for i in range(n):
		if i % 2 == 0:
			x = min(x, l[i])
			cnt1 += 1
		else:
			y = min(y, l[i])
			cnt2 += 1
		som += l[i]
		if i > 0:
			ans = min(ans, som + x * (n - cnt1) + y * (n - cnt2))
	print(ans)


t = int(input())
for g in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	a = [s[0], s[1]]
	mn = [s[0], s[1]]
	cnt = [1, 1]
	ans = (s[0] + s[1]) * n
	for i in range(2, n):
		mn[i % 2] = min(mn[i % 2], s[i])
		a[i % 2] += s[i]
		cnt[i % 2] += 1
		ans = min(ans, a[0] - mn[0] + (n - cnt[0] + 1) * mn[0] + a[1] - mn[1] + (n - cnt[1] + 1) * mn[1])
	print(ans)


for _ in range(int(input())):
	x = int(input())
	zoo = list(map(int, input().split()))
	ans = zoo[0] * x + zoo[1] * x
	sum1 = zoo[0]
	sum2 = zoo[1]
	min1 = zoo[0]
	min2 = zoo[1]
	count1 = 1
	count2 = 1
	p2 = zoo[1] * x
	for i in range(2, x):
		if i % 2 == 0:
			sum1 += zoo[i]
			count1 += 1
			min1 = min(min1, zoo[i])
			p1 = sum1 + min1 * (x - count1)
		else:
			sum2 += zoo[i]
			count2 += 1
			min2 = min(min2, zoo[i])
			p2 = sum2 + min2 * (x - count2)
		ans = min(ans, p1 + p2)
	print(ans)


for ad in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	m1 = l[0]
	m2 = l[1]
	ans = m1 * n + m2 * n
	x = ans
	for i in range(2, n):
		if i % 2 == 0:
			if l[i] < m1:
				ans -= m1 * (n - i // 2)
				m1 = l[i]
				ans += m1 * (n - i // 2)
			else:
				ans += l[i] - m1
		elif l[i] < m2:
			ans -= m2 * (n - i // 2)
			m2 = l[i]
			ans += m2 * (n - i // 2)
		else:
			ans += l[i] - m2
		x = min(x, ans)
	print(x)


import math

def solve(n, C):
	sums = math.inf
	min_even = min_odd = min_e = min_o = math.inf
	even_sum = even_count = odd_sum = odd_count = 0
	for (i, c) in enumerate(C):
		if i % 2 == 0:
			even_sum += c
			even_count += 1
			min_e = min(c, min_e)
			min_even = even_sum + min_e * (n - even_count)
			if min_odd + min_even < sums:
				sums = min_odd + min_even
		else:
			odd_sum += c
			odd_count += 1
			min_o = min(c, min_o)
			min_odd = odd_sum + min_o * (n - odd_count)
			if min_odd + min_even < sums:
				sums = min_odd + min_even
	return sums
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split(' ')))
	print(solve(n, c))


for testis in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	(x, y) = (c[0], c[1])
	res = [x * n + y * n]
	r = 0
	for i in range(2, n):
		if i % 2 == 0:
			if c[i] < x:
				r += x
				x = c[i]
			else:
				r += c[i]
			res.append(x * (n - i // 2) + y * (n - i // 2 + 1) + r)
		else:
			if c[i] < y:
				r += y
				y = c[i]
			else:
				r += c[i]
			res.append(x * (n - i // 2) + y * (n - i // 2) + r)
	print(min(res))


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	cost = float('inf')
	(u1, r1) = (n, n)
	a = 0
	b = 0
	i = 0
	(s1, s2) = (float('inf'), float('inf'))
	while i < n:
		if i % 2 == 0:
			s1 = min(s1, l[i])
			cost = min(cost, a + b + s1 * r1 + s2 * u1)
			r1 -= 1
			a += l[i]
		else:
			s2 = min(s2, l[i])
			cost = min(cost, a + b + s2 * u1 + s1 * r1)
			u1 -= 1
			b += l[i]
		i += 1
	print(cost)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	l = list(map(int, sys.stdin.readline().split()))
	right = l[0]
	up = l[1]
	su = l[1] + l[0]
	udone = 1
	rdone = 1
	low = l[1] * n + l[0] * n
	for i in range(2, n):
		su += l[i]
		if i % 2 == 0:
			right = min(l[i], right)
			rdone += 1
			low = min(low, (n - rdone) * right + (n - udone) * up + su)
		else:
			up = min(l[i], up)
			udone += 1
			low = min(low, (n - rdone) * right + (n - udone) * up + su)
	print(low)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def read_int_list():
	return list(map(int, input().split()))

def read_int_tuple():
	return tuple(map(int, input().split()))

def read_int():
	return int(input())
t = read_int()
for _ in range(t):
	n = read_int()
	c = read_int_list()
	hor = c[0::2]
	ver = c[1::2]
	ans = -1
	(min_cost_h, min_cost_v) = (-1, -1)
	(cum_sum_h, cum_sum_v) = (0, 0)
	(cost_each_h, cost_each_v) = (0, 0)
	total_cost_list_h = []
	total_cost_list_v = []
	(cur_cost_h, cur_cost_v) = (-1, -1)
	for (end_pos, value) in enumerate(c):
		if end_pos % 2 == 0:
			h_pos = end_pos // 2
			h_value = value
			if min_cost_h < 0 or min_cost_h > h_value:
				min_cost_h = h_value
			cost_each_h += hor[h_pos]
			cost_peak = (n - h_pos - 1) * min_cost_h
			cost_hor = cost_each_h + cost_peak
			cur_cost_h = cost_hor
		else:
			v_pos = (end_pos - 1) // 2
			v_value = ver[v_pos]
			if min_cost_v < 0 or min_cost_v > v_value:
				min_cost_v = v_value
			cost_each_v += ver[v_pos]
			cost_peak = (n - v_pos - 1) * min_cost_v
			cost_ver = cost_each_v + cost_peak
			cur_cost_v = cost_ver
		if cur_cost_h < 0 or cur_cost_v < 0:
			continue
		cost = cur_cost_h + cur_cost_v
		if ans < 0 or ans > cost:
			ans = cost
	print(ans)


INF = 10 ** 20

def solve():
	n = int(input())
	(*c,) = map(int, input().split())
	min_odd = INF
	min_ev = INF
	sum_odd = 0
	sum_ev = 0
	ans = INF
	cnt_o = n
	cnt_e = n
	for (i, x) in enumerate(c):
		if i % 2 == 0:
			min_odd = min(min_odd, x)
			sum_odd += x
			cnt_o -= 1
		else:
			min_ev = min(min_ev, x)
			sum_ev += x
			cnt_e -= 1
		ans = min(ans, sum_ev + sum_odd + min_ev * cnt_e + min_odd * cnt_o)
	return ans
t = int(input())
for _ in range(t):
	print(solve())


from __future__ import division, print_function
import os, sys
from io import BytesIO, IOBase
from collections import deque, Counter, OrderedDict, defaultdict
from itertools import filterfalse, permutations, combinations
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().strip().split())

def msi():
	return map(str, input().strip().split())

def li():
	return list(mi())

def dmain():
	sys.setrecursionlimit(1000000)
	threading.stack_size(1024000)
	thread = threading.Thread(target=main)
	thread.start()
from collections import deque, Counter, OrderedDict, defaultdict
from math import *
from itertools import permutations, combinations
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
vow = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[1]

def sort2(l):
	return sorted(l, key=getKey, reverse=True)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def ceil(x, y):
	if x % y == 0:
		return x // y
	else:
		return x // y + 1

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def expo(x, y, m):
	if y == 0:
		return 1
	elif y % 2 == 0:
		return expo(x * x % m, y / 2, m)
	else:
		return x * expo(x * x % m, (y - 1) / 2, m) % m

def gcd(a, b):
	if a == 0:
		return (b, 0, 1)
	(gc, x1, y1) = gcd(b % a, a)
	x = y1 - b // a * x1
	y = x1
	return (gc, x, y)

def sieve(n):
	arr = [True] * (n + 1)
	arr[0] = False
	arr[1] = False
	for i in range(4, n + 1, 2):
		val = False
	for i in range(3, int(sqrt(n)) + 1, 2):
		if val == True:
			for j in range(i * i, n + 1, i):
				arr[j] = False
	return arr

def modInverse(x, y):
	(gc, x1, y1) = gcd(x, y)
	return (y1 + y) % y

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def read():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def main():
	for _ in range(ii()):
		n = ii()
		arr = li()
		a = [arr[0]]
		b = [arr[1]]
		amin = arr[0]
		bmin = arr[1]
		asum = arr[0]
		bsum = arr[1]
		alen = 1
		blen = 1
		help = amin * (n - alen) + asum + bmin * (n - blen) + bsum
		for i in range(2, n):
			val = arr[i]
			if i % 2 == 0:
				a.append(val)
				amin = min(val, amin)
				asum += val
				alen += 1
			else:
				b.append(val)
				bmin = min(bmin, val)
				bsum += val
				blen += 1
			help = min(amin * (n - alen) + asum + bmin * (n - blen) + bsum, help)
		print(help)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	b0 = 10 ** 10
	b1 = 10 ** 10
	sm = 0
	res = 10 ** 18
	for i in range(n):
		if i % 2 == 0:
			if c[i] < b0:
				b0 = c[i]
		elif c[i] < b1:
			b1 = c[i]
		sm += c[i]
		c0 = (i + 2) // 2
		c1 = (i + 1) // 2
		res = min(res, sm + (n - c0) * b0 + (n - c1) * b1)
	print(res)


import sys
from collections import defaultdict, Counter
inf = 1000000007
t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	ans = inf * inf
	sum_odd = 0
	sum_even = 0
	kol_odd = 0
	kol_even = 0
	min_odd = inf
	min_even = inf
	for i in range(n):
		if i % 2 == 0:
			sum_odd += c[i]
			kol_odd += 1
			min_odd = min(min_odd, c[i])
		else:
			sum_even += c[i]
			kol_even += 1
			min_even = min(min_even, c[i])
		if i > 0:
			f = sum_odd + sum_even + min_even * (n - kol_even) + min_odd * (n - kol_odd)
			ans = min(ans, f)
	print(ans)


for u in range(int(input())):
	n = int(input())
	x = [int(w) for w in input().split()]
	ans = n * x[0] + n * x[1]
	s1 = x[0]
	s2 = x[1]
	m1 = x[0]
	m2 = x[1]
	l1 = 1
	l2 = 1
	for k in range(2, n):
		if k % 2 == 0:
			s1 += x[k]
			l1 += 1
			m1 = min(m1, x[k])
		else:
			s2 += x[k]
			l2 += 1
			m2 = min(m2, x[k])
		temp = s1 + (n - l1) * m1 + (s2 + (n - l2) * m2)
		ans = min(ans, temp)
	print(ans)


import os
import sys
import math
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def dijkstra(start, distance, path, n):
	visited = [False for _ in range(n)]
	distance[start] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not visited[v] and (v == -1 or distance[j] < distance[v]):
				v = j
		if distance[v] == math.inf:
			break
		visited[v] = True
		for edge in adj[v]:
			destination = edge[0]
			weight = edge[1]
			if distance[v] + weight < distance[destination]:
				distance[destination] = distance[v] + weight
				path[destination] = v

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 1
	while x * x <= n:
		if n % x == 0:
			if n // x == x:
				factors.append(x)
			else:
				factors.append(x)
				factors.append(n // x)
		x += 1
	return factors

def main():
	try:
		for _ in range(inp()):
			n = inp()
			a = inlt()
			(mn1, mn2) = (a[0], a[1])
			le = [n, n]
			(sum1, sum2) = (0, 0)
			ans = math.inf
			for i in range(n):
				if i % 2:
					mn2 = min(mn2, a[i])
					sum2 += a[i]
					le[1] -= 1
				else:
					mn1 = min(mn1, a[i])
					sum1 += a[i]
					le[0] -= 1
				ans = min(ans, sum1 + sum2 + mn1 * le[0] + mn2 * le[1])
			print(ans)
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
for _ in range(int(input())):
	n = int(input())
	c = tuple(map(int, sys.stdin.readline().split()))
	(x, y) = (c[0], c[1])
	res = [x * n + y * n]
	r = 0
	for i in range(2, n):
		if i % 2 == 0:
			if c[i] < x:
				r += x
				x = c[i]
			else:
				r += c[i]
			res.append(x * (n - i // 2) + y * (n - i // 2 + 1) + r)
		else:
			if c[i] < y:
				r += y
				y = c[i]
			else:
				r += c[i]
			res.append(x * (n - i // 2) + y * (n - i // 2) + r)
	print(min(res))