You are an ambitious king who wants to be the Emperor of The Reals. But to do that, you must first become Emperor of The Integers.

Consider a number axis. The capital of your empire is initially at $0$. There are $n$ unconquered kingdoms at positions $0<x_1<x_2<\ldots<x_n$. You want to conquer all other kingdoms.

There are two actions available to you:

You can change the location of your capital (let its current position be $c_1$) to any other conquered kingdom (let its position be $c_2$) at a cost of $a\cdot |c_1-c_2|$.

From the current capital (let its current position be $c_1$) you can conquer an unconquered kingdom (let its position be $c_2$) at a cost of $b\cdot |c_1-c_2|$. You cannot conquer a kingdom if there is an unconquered kingdom between the target and your capital.

Note that you cannot place the capital at a point without a kingdom. In other words, at any point, your capital can only be at $0$ or one of $x_1,x_2,\ldots,x_n$. Also note that conquering a kingdom does not change the position of your capital.

Find the minimum total cost to conquer all kingdoms. Your capital can be anywhere at the end.


-----Input-----

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

The first line of each test case contains $3$ integers $n$, $a$, and $b$ ($1 \leq n \leq 2 \cdot 10^5$; $1 \leq a,b \leq 10^5$).

The second line of each test case contains $n$ integers $x_1, x_2, \ldots, x_n$ ($1 \leq x_1 < x_2 < \ldots < x_n \leq 10^8$).

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a single integer  — the minimum cost to conquer all kingdoms.


-----Examples-----

Input
4
5 2 7
3 5 12 13 21
5 6 3
1 5 6 21 30
2 9 3
10 15
11 27182 31415
16 18 33 98 874 989 4848 20458 34365 38117 72030
Output
173
171
75
3298918744


-----Note-----

Here is an optimal sequence of moves for the second test case:

Conquer the kingdom at position $1$ with cost $3\cdot(1-0)=3$.

Move the capital to the kingdom at position $1$ with cost $6\cdot(1-0)=6$.

Conquer the kingdom at position $5$ with cost $3\cdot(5-1)=12$.

Move the capital to the kingdom at position $5$ with cost $6\cdot(5-1)=24$.

Conquer the kingdom at position $6$ with cost $3\cdot(6-5)=3$.

Conquer the kingdom at position $21$ with cost $3\cdot(21-5)=48$.

Conquer the kingdom at position $30$ with cost $3\cdot(30-5)=75$.

The total cost is $3+6+12+24+3+48+75=171$. You cannot get a lower cost than this.

Difficulty: MEDIUM
Tags: Sorting

Implementation

Complete search

Greedy algorithms

Dynamic programming

Mathematics
Skill types: Dynamic programming

Sorting

Complete search

Greedy algorithms

Starter code:

Solutions:
def solve():
	(n, a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	ans = 10 ** 18
	suffix = 0
	for i in range(n - 1, -1, -1):
		prefix = x[i]
		ans = min(ans, (a + b) * prefix + b * suffix)
		if i == 0:
			suffix += x[i] * n
		else:
			suffix += (x[i] - x[i - 1]) * (n - i)
	ans = min(ans, b * suffix)
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def solve(n, a, b, xs):
	S = sum(xs)
	res = b * S
	for i in range(n):
		S -= xs[i]
		tmp = a * xs[i] + b * (S - (n - i - 2) * xs[i])
		res = min(res, tmp)
	return res
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	xs = [*map(int, input().split())]
	res = solve(n, a, b, xs)
	print(res)


def solve():
	(n, a, b) = list(map(int, input().split(' ')))
	x = [0] + list(map(int, input().split(' ')))
	mn = float('inf')
	sum = x[n]
	for i in range(n - 1, -1, -1):
		res = b * x[i] + a * x[i] + b * (sum - (n - i) * x[i])
		sum += x[i]
		mn = min(res, mn)
	print(mn)
for t in range(int(input())):
	solve()


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

def solve():
	(n, a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	q = deque([])
	ans = idx = curr = 0
	while idx < n:
		if not q or a > (n - idx) * b:
			q.append(idx)
			ans += (arr[q[-1]] - curr) * b
			idx += 1
			continue
		ans += (arr[q[0]] - curr) * a
		curr = arr[q.popleft()]
	print(ans)
for _ in range(int(input())):
	solve()


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	positions = [0]
	positions.extend(map(int, input().split()))
	cost = 0
	capital = 0
	for i in range(1, n + 1):
		if b * (n - i - 1) > a - b:
			cost += (a + b) * (positions[i] - positions[i - 1])
			capital = positions[i]
		else:
			cost += b * (positions[i] - capital)
	print(cost)


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	ls = list(map(int, input().split()))
	ls.insert(0, 0)
	n += 1
	sum = 0
	x = ls[n - 1]
	lastCost = x * (a + b)
	for j in range(n - 1, -1, -1):
		x = ls[j]
		cost = x * (a + b) + b * (sum - (n - j - 1) * x)
		if cost > lastCost:
			break
		else:
			lastCost = cost
		sum += x
	print(str(lastCost))


def solve():
	(n, a, b) = map(int, input().split())
	x = [0] + list(map(int, input().split()))
	n += 1
	s = sum(x[1:])
	mx = float('inf')
	for i in range(n):
		v = x[i]
		cr = (a + b) * v
		s -= v
		cr += (s - (n - i - 1) * v) * b
		mx = min(mx, cr)
	print(mx)
tc = int(input())
for _ in range(tc):
	solve()


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

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

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

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

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		(n, a, b) = sep()
		arr = lis()
		p = sum(arr)
		ans = b * p
		for i in range(n):
			p -= arr[i]
			ans = min(ans, (a + b) * arr[i] + (p - (n - i - 1) * arr[i]) * b)
		print(ans)
main()


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	positions = [0]
	positions.extend(map(int, input().split()))
	cost = 0
	capital = 0
	for i in range(1, n + 1):
		if b * (n - i - 1) > a - b:
			cost += (a + b) * (positions[i] - positions[i - 1])
			capital = positions[i]
		else:
			cost += b * (positions[i] - capital)
	print(cost)


cases = int(input())
for case in range(cases):
	(n, b, a) = map(int, input().split())
	kingdoms = list(map(int, input().split()))
	total = a * sum(kingdoms)
	index = 0
	cur = 0
	for item in kingdoms:
		difference = (item - cur) * b - a * (item - cur) * (n - 1 - index)
		if difference < 0:
			total += difference
			cur = item
			index += 1
		else:
			break
	print(total)


import math
import sys, io, os
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
flush = lambda : sys.stdout.flush()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	(size, x, y) = ari()
	arr = [0]
	arr += ari()
	sp = sum(arr)
	ans = float('inf')
	size += 1
	for i in range(size - 1):
		temp = (x + y) * arr[i]
		sp -= arr[i]
		cap = size - i - 1
		temp += (sp - cap * arr[i]) * y
		ans = min(ans, temp)
	print(ans)
	return
for _ in range(test_case):
	ans()


for i in range(int(input())):
	l = list(map(int, input().split()))
	n = l[0]
	a = l[1]
	b = l[2]
	l = [0]
	l.extend(list(map(int, input().split())))
	l1 = [b * sum(l)]
	a1 = 0
	b1 = 1
	for j in range(n):
		l1.append(l1[j] + a * (l[j + 1] - l[j]) - (n - j - 1) * b * (l[j + 1] - l[j]))
	print(min(l1))


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l = [0] + l
	ans = [0 for i in range(n)]
	ans[0] = sum(l) * b
	for i in range(1, len(ans)):
		ans[i] = ans[i - 1] + (l[i] - l[i - 1]) * a - (n - i) * b * (l[i] - l[i - 1])
	print(min(ans))


t = int(input())
while t:
	t -= 1
	(n, a, b) = map(int, input().split())
	x = [0] + [*map(int, input().split())]
	l = [sum(x) * b]
	for i in range(1, n):
		c = l[-1] + a * (x[i] - x[i - 1]) - (x[i] - x[i - 1]) * (n - i) * b
		if c > l[-1]:
			break
		l.append(c)
	print(l[-1])


import collections
import math
import sys
need_two = 0

def main():
	(n, a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	s = sum(x)
	res = 2 ** 100
	x.insert(0, 0)
	n += 1
	for i in range(n):
		cur = (a + b) * x[i]
		s -= x[i]
		cur += (s - (n - i - 1) * x[i]) * b
		res = min(res, cur)
	print(res)
t = int(input())
while t > 0:
	main()
	t -= 1


for _ in range(int(input())):
	(n, a, b) = map(int, input().split(' '))
	c = list(map(int, input().split(' ')))
	sc = sum(c)
	sci = 0
	ans = b * sc
	for i in range(n):
		sc -= c[i]
		val = (a + b) * c[i] + b * (sc - c[i] * (len(c) - i - 1))
		if val <= ans:
			ans = val
	print(ans)


def main():
	T = int(input())
	for _ in range(T):
		(n, a, b) = list(map(int, input().strip().split(' ')))
		v = list(map(int, input().strip().split(' ')))
		sum = 0
		for i in range(len(v)):
			sum += v[i]
		res = 1e+18
		v.insert(0, 0)
		cur = 0
		for i in range(0, n):
			cur = (a + b) * v[i]
			sum -= v[i]
			cur += (sum - (n - i) * v[i]) * b
			res = min(res, cur)
		print(res)
main()


def solve():
	(N, A, B) = map(int, input().split())
	x = list(map(int, input().split()))
	x.append(0)
	x.insert(0, 0)
	N += 1
	COSTA = 0
	COSTB = 0
	COSTC = 0
	ANS = 1 << 60
	for i in range(N):
		COSTB += x[i] * B
	for i in range(0, N):
		COSTA = x[i] * A
		COSTB -= (N - i) * (x[i] - x[i - 1]) * B
		COSTC = x[i] * B
		ANS = min(ANS, COSTA + COSTB + COSTC)
	print(ANS)
t = int(input())
while t > 0:
	solve()
	t -= 1


for test in range(int(input())):
	(n, a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	sm = sum(x)
	ans = sm * b
	s = 0
	for i in range(n):
		s += x[i]
		ans = min(ans, (a + b) * x[i] + (sm - s - (n - i - 1) * x[i]) * b)
	print(ans)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	sumX = 0
	for num in x:
		sumX += num
	sumPrev = 0
	minimum = 2 * 10 ^ 13 + 1
	for i in range(n - 1):
		if i != 0:
			sumPrev += x[i - 1]
		additional = a * x[i] - b * (sumPrev + x[i] * (n - i - 1))
		if additional < minimum:
			minimum = additional
	print(min(b * sumX, b * sumX + minimum))


for i in range(int(input())):
	(n, a, b) = map(int, input().split())
	vh = list(map(int, input().split()))
	sm = sum(vh)
	rs = sm * b
	s = 0
	for j in range(n):
		s += vh[j]
		rs = min(rs, (a + b) * vh[j] + (sm - s - (n - j - 1) * vh[j]) * b)
	print(rs)


def solve():
	(n, a, b) = list(map(int, input().split()))
	arr = [0] + list(map(int, input().split()))
	second_arr = [0] + [abs(arr[i] - arr[i + 1]) for i in range(n)]
	s = sum(arr)
	iter_sum = 0
	min_ = float('inf')
	n = len(arr)
	length = n
	for i in range(length):
		s -= arr[i]
		n -= 1
		value = abs(s - n * arr[i])
		iter_sum += second_arr[i]
		min_ = min(min_, (a + b) * iter_sum + b * value)
	return min_
for _ in range(int(input())):
	print(solve())


t = int(input())

def solve(n, a, b, X):
	dists = [X[0]]
	for x in X[1:]:
		dists.append(x + dists[-1])
	lowest = dists[-1] * b
	for i in range(n - 1):
		current = a * X[i]
		current += b * X[i + 1]
		current += (dists[-1] - dists[i + 1] - (n - i - 2) * X[i]) * b
		lowest = min(current, lowest)
	return lowest
for _ in range(t):
	(n, a, b) = map(int, input().split())
	X = list(map(int, input().split()))
	print(solve(n, a, b, X))


t = int(input())
for i in range(t):
	(n, a, b) = [int(i) for i in input().split()]
	positions = [int(i) for i in input().split()]
	s = sum(positions)
	finals = []
	neg = 0
	for i in range(len(positions)):
		neg += positions[i]
		cost = 0
		cost += positions[i] * (a + b)
		cost += (s - neg - (n - i - 1) * positions[i]) * b
		finals.append(cost)
	finals.append(sum(positions) * b)
	print(min(finals))


import sys

def solve():
	inp = sys.stdin.readline
	(n, a, b) = map(int, inp().split())
	x = list(map(int, inp().split()))
	s = sum(x)
	r = 0
	now = 0
	for i in range(n):
		s -= x[i]
		r += (x[i] - now) * b
		if (s - now * (n - i - 1)) * b >= (s - x[i] * (n - i - 1)) * b + (x[i] - now) * a:
			r += (x[i] - now) * a
			now = x[i]
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	v = list(map(int, input().split()))
	v = [0] + v
	s = sum(v)
	res = int(1e+18)
	n += 1
	for i in range(n):
		curr = (a + b) * v[i]
		s -= v[i]
		curr += (s - (n - i - 1) * v[i]) * b
		res = min(res, curr)
	print(res)


def mincost(nums):
	presum = [0] * (n + 1)
	for i in range(1, n + 1):
		presum[i] = presum[i - 1] + nums[i - 1]
	ans = b * presum[n]
	for i in range(n):
		tmp = b * nums[i] + a * nums[i] + b * (presum[n] - presum[i + 1]) - (n - i - 1) * b * nums[i]
		ans = min(ans, tmp)
	return ans
t = int(input())
for _ in range(t):
	(n, a, b) = [int(x) for x in input().split()]
	nums = [int(x) for x in input().split()]
	print(mincost(nums))


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	array = list(map(int, input().split()))
	sm = sum(array)
	sums = [sm]
	for i in array:
		sm -= i
		sums.append(sm)
	mn = sums[0] * b
	for i in range(n):
		tp = array[i] * a
		tp += (sums[i + 1] - (n - i - 2) * array[i]) * b
		mn = min(mn, tp)
	print(mn)


t = int(input())
for qwer in range(t):
	(n, a, b) = map(int, input().split())
	l = ['0'] + input().split()
	sp = list(map(int, l))
	ind = 0
	colvo = n
	for i in range(n - 1):
		c = sp[i + 1] - sp[ind]
		if c * (colvo - 1) * b > c * a:
			ind = i + 1
		colvo -= 1
	if a <= b:
		s = 0
		for i in range(n):
			s += (sp[i + 1] - sp[i]) * (a + b)
		s -= (sp[-1] - sp[-2]) * a
	else:
		s = 0
		for i in range(n):
			if i < ind:
				s += (sp[i + 1] - sp[i]) * (b + a)
			else:
				s += (sp[i + 1] - sp[ind]) * b
	print(s)


import math as m
t = int(input())
for _ in range(0, t):
	(n, k, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.insert(0, 0)
	p = 0
	for i in range(0, n + 1):
		p += l[i]
	r = 1e+18
	for i in range(0, n + 1):
		c = (k + b) * l[i]
		p -= l[i]
		c += (p - (n - i) * l[i]) * b
		r = min(r, c)
	print(r)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	a = inputs[1]
	b = inputs[2]
	list1 = [int(num) for num in input().split()]
	c = 0
	cost_now = 0
	now = 0
	cost = 0
	for i in range(0, len(list1)):
		point = list1[i]
		cost += (point - now) * b
		c += 1
		if (point - now) * a <= (point - now) * b * (n - c):
			cost += (point - now) * a
			now = point
	print(cost)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	lst = list(map(int, input().split()))
	pos = 0
	llstr = [0]
	s2 = sum(lst)
	mini = sum(lst) * b
	for i in range(n):
		llstr.append((a + b) * (lst[i] - pos) + llstr[-1])
		pos = lst[i]
		s2 -= lst[i]
		s3 = s2 - pos * (n - 1 - i)
		mini = min(s3 * b + llstr[-1], mini)
		pos = lst[i]
	print(mini)


for _ in range(int(input())):
	(n, a, b) = map(int, input().split())
	arr = [0]
	my = [int(i) for i in input().split()]
	arr.extend(my)
	tot = sum(arr) * b
	ans = 0
	pre = 0
	post = 1
	for i in range(1, len(arr)):
		while post < i:
			save = (arr[post] - arr[pre]) * b * (len(arr) - i)
			ext = (arr[post] - arr[pre]) * a
			if save >= ext:
				tot -= save - ext
				pre = post
				post += 1
			else:
				break
	print(tot)


t = int(input())
for i in range(t):
	(n, a, b) = map(int, input().split())
	lst = list(map(int, input().split()))
	pre = [lst[0]]
	for j in range(1, n):
		pre.append(pre[-1] + lst[j])
	ans = []
	dif = [lst[0]]
	for j in range(1, n):
		dif.append(lst[j] - lst[j - 1])
	ans.append(pre[-1] * b)
	predif = [dif[0]]
	for j in range(1, len(dif)):
		predif.append(predif[-1] + dif[j])
	for j in range(n):
		q = (a + b) * predif[j]
		w = (pre[-1] - pre[j] - (n - j - 1) * lst[j]) * b
		ans.append(q + w)
	print(min(ans))


import sys
input = sys.stdin.readline
from math import ceil, floor, gcd

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

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

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

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

def isPrime(n):
	if n == 1:
		return 0
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return 0
	return 1
t = inp()
for _ in range(t):
	(n, a, b) = map(int, input().split())
	s = lis()
	dp = [0 for i in range(n)]
	k = 0
	m = 1
	for i in range(n - 1, 0, -1):
		k += (s[i] - s[i - 1]) * m
		m += 1
		dp[i] = k * b
	k += (s[0] - 0) * m
	dp[0] = k * b
	capi = 0
	ans = float('inf')
	now = 0
	for i in range(n):
		tobe = now + dp[i]
		ans = min(ans, tobe)
		now += (s[i] - capi) * b
		now += (s[i] - capi) * a
		capi = s[i]
	ans = min(now, ans)
	print(ans)


for iii in range(int(input())):
	(n, a, b) = map(int, input().split())
	q = list(map(int, input().split()))
	q1 = [0] + q
	for i in range(1, n + 1):
		q1[i] += q1[i - 1]
	bwd_sum = 0
	shift_cap = 0
	fwd = 0
	summ = 123456789876543212345678
	for i in range(n + 1):
		if i == 0:
			bwd_sum = 0
		elif i == 1:
			bwd_sum = q[i - 1] * b
		else:
			bwd_sum = bwd_sum + (q[i - 1] - q[i - 2]) * b
		if i == 0:
			shift_cap = 0
		else:
			shift_cap = q[i - 1] * a
		if i == 0:
			fwd = q1[n] * b
		else:
			fwd = (q1[n] - q1[i] - q[i - 1] * (n - i)) * b
		summ = min(summ, fwd + bwd_sum + shift_cap)
	print(summ)


t = int(input())
while t > 0:
	c = input().split()
	(n, a, b) = (int(c[0]), int(c[1]), int(c[2]))
	x = input().split()
	for i in range(n):
		x[i] = int(x[i])
	x = [0] + x
	ans = 0
	cur = 0
	ind = 0
	for i in range(1, n + 1):
		while ind < i - 1:
			if b * (x[ind + 1] - x[ind]) * (n + 1 - i) >= a * (x[ind + 1] - x[ind]):
				ans += a * (x[ind + 1] - x[ind])
				ind += 1
			else:
				break
		ans += b * (x[i] - x[ind])
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, a, b) = [int(x) for x in input().split()]
	v = [int(x) for x in input().split()]
	v = [0] + v
	con = [0] * (n + 1)
	for i in range(1, n + 1):
		con[i] = b * (v[i] - 0)
	for i in range(n - 1, -1, -1):
		con[i] += con[i + 1]
	cost = 0
	val = 0
	ans = 10 ** 18
	for i in range(n):
		cost = v[i] * a
		if i != 0:
			val += (v[i] - v[i - 1]) * b
		cost += val
		rem = n - i
		rem *= v[i] * b
		cost += con[i + 1] - rem
		ans = min(ans, cost)
	print(ans)


iter = int(input())
for _ in range(iter):
	lst = list(map(int, input().split()))
	kingdoms = list(map(int, input().split()))
	min_cost = 0
	prefix = [0] * lst[0]
	prefix[0] = kingdoms[0]
	for i in range(1, lst[0]):
		prefix[i] += kingdoms[i] + prefix[i - 1]
	min_cost = lst[2] * prefix[-1]
	for i in range(lst[0] - 1):
		curr_cost = kingdoms[0] * (lst[1] + lst[2])
		curr_cost += (kingdoms[i] - kingdoms[0]) * (lst[2] + lst[1])
		curr_cost += -kingdoms[i] * lst[2] * (lst[0] - 1 - i)
		curr_cost += (prefix[-1] - prefix[i]) * lst[2]
		min_cost = min(curr_cost, min_cost)
	print(min_cost)


t = int(input())
for _ in range(t):
	(n, a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	help = [0] * n
	for i in reversed(range(n - 1)):
		help[i] = help[i + 1] + arr[i + 1]
	cost = b * arr[0]
	index = 0
	capital = 0
	while index < n - 1:
		if b * (help[index] - capital * (n - (index + 1))) > a * (arr[index] - capital) + b * (help[index] - arr[index] * (n - (index + 1))):
			cost += a * (arr[index] - capital)
			capital = arr[index]
		cost += b * (arr[index + 1] - capital)
		index += 1
	print(cost)


for _ in ' ' * int(input()):
	(n, a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	sf = [0] * n
	pr = [0] * n
	sf[-1] = x[-1]
	pr[0] = x[0]
	for i in range(1, n):
		pr[i] = pr[i - 1] + x[i]
	for i in range(n - 2, -1, -1):
		sf[i] = sf[i + 1] + x[i]
	mnc = b * sum(x)
	prc = 0
	xc = 0
	xi = -1
	for i in range(n - 1):
		if xi == -1:
			temp = b * pr[i]
		else:
			temp = b * (pr[i] - pr[xi] - (i - xi) * xc)
		crc = prc + a * (x[i] - xc) + temp
		if crc + b * (sf[i + 1] - (n - i - 1) * x[i]) <= mnc:
			mnc = crc + b * (sf[i + 1] - (n - i - 1) * x[i])
			prc = crc
			xc = x[i]
			xi = i
	print(mnc)