Mark is an undergraduate student and he is interested in rotation. A conveyor belt competition is going on in the town which Mark wants to win. In the competition, there's A conveyor belt which can be represented as a strip of 1xN blocks. Each block has a number written  on it. The belt keeps rotating in such a way that after each rotation, each block is shifted to left of it and the first block goes to last position.  

There is a switch near the conveyer belt which can stop the belt. Each participant would be given a single chance to stop the belt and his PMEAN would be calculated.  

PMEAN is calculated using the sequence which is there on the belt when it stops. The participant having highest PMEAN is the winner. There can be multiple winners.

Mark wants to be among the winners. What PMEAN he should try to get which guarantees him to be the winner.

$\textit{PMEAN}=\sum_{i=1}^{n}i\times a[i]$

where ${a}$ represents the configuration of conveyor belt when it is stopped. Indexing starts from 1.  

Input Format 

First line contains N denoting the number of elements on the belt. 

Second line contains N space separated integers.  

Output Format 

Output the required PMEAN  

Constraints 

1 ≤ N ≤ 10^{6} 

-10^{9} ≤ each number ≤ 10^{9} 

For any rotation, PMEAN will always lie within the range of 64-bit signed integer.  

Sample Input  

3
20 30 10 

Sample Output  

140

Explanation  

Number on top can be written in these manners. 

Initial numbers on belt, 20 30 10  PMEAN = 1x20 + 2x30 + 3x10 = 110 

After first rotation,     30 10 20  PMEAN = 1x30 + 2x10 + 3x20 = 110 

After second rotation,     10 20 30  PMEAN = 1x10 + 2x20 + 3x30 = 140 

So maximum possible value will be 140.

Difficulty: MEDIUM
Tags: Matrices

Starter code:

Solutions:
n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
cur_val = ans = sum((a[i] * (i + 1) for i in range(n)))
for i in range(n):
	cur_val = cur_val - sum_a + a[i] * n
	ans = max(ans, cur_val)
print(ans)


import sys

def read_numbers(line=None):
	if line is None:
		line = sys.stdin.readline()
	return [int(x) for x in line.split()]

def rotation(blocks):
	total_sum = sum(blocks)
	pmean = sum(((i + 1) * block for (i, block) in enumerate(blocks)))
	max_pmean = pmean
	for block in blocks:
		pmean = pmean - total_sum + block * len(blocks)
		max_pmean = max(max_pmean, pmean)
	return max_pmean
n = read_numbers()[0]
blocks = read_numbers()
print(rotation(blocks))


def f(A):
	s = sum(A)
	k = 0
	for i in range(len(A)):
		k += (i + 1) * A[i]
	rt = k
	for i in range(len(A) - 1, -1, -1):
		k += s - A[i] * len(A)
		if k > rt:
			rt = k
	return rt
input()
print(f(list(map(int, input().split()))))


n = int(input())
belt = [int(i) for i in str(input()).split()]
s = sum(belt)
pmean = 0
for (i, j) in enumerate(belt):
	pmean += (i + 1) * j
max_pmean = pmean
for i in range(n):
	pmean = pmean - s + n * belt[i]
	max_pmean = max(max_pmean, pmean)
print(max_pmean)


def main():
	n = int(input())
	li = list(map(int, input().split()))
	sum = 0
	pmean = 0
	for i in range(n):
		sum += li[i]
		pmean += li[i] * (i + 1)
	maxmean = pmean
	for i in range(n - 1):
		pmean = pmean - sum + n * li[i]
		if pmean > maxmean:
			maxmean = pmean
	print(maxmean)
main()


import sys
data = sys.stdin.readlines()
numbers = [int(n) for n in data[1].split()]
nBeltElements = len(numbers)
PMEANmax = -1e+200
PMEAN = sum([n * (i + 1) for (i, n) in enumerate(numbers)])
numbers_sum = sum(numbers)
for iStart in range(nBeltElements):
	PMEANmax = max(PMEANmax, PMEAN)
	PMEAN = PMEAN - numbers_sum + numbers[iStart] * nBeltElements
print(PMEANmax)


N = int(input())
nums = [int(n) for n in input().split()]
pmean = 0
for (i, n) in enumerate(nums):
	pmean += (i + 1) * n
nums_sum = sum(nums)
pmean_ = pmean
for n in nums:
	pmean_ -= nums_sum - n * N
	pmean = max(pmean, pmean_)
print(pmean)


n = int(input())
nums = [int(x) for x in input().split()]
s = sum(nums)
t = sum((i * v for (i, v) in enumerate(nums, 1)))
m = t
for i in range(n):
	t -= s
	t += n * nums[i]
	m = max(m, t)
print(m)


N = int(input())
c = [int(v) for v in input().split()]
cs = sum(c)
wcs = sum([(i + 1) * e for (i, e) in enumerate(c)])
wcsm = wcs
for i in c:
	wcs = wcs - cs + i * N
	wcsm = max(wcs, wcsm)
print(wcsm)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


n = int(input())
lst = list(map(int, input().split()))
s = sum([(i + 1) * lst[i] for i in range(n)])
ss = sum(lst)
index = 0
maxS = s
while index < n - 1:
	s = s - ss + n * lst[index]
	index += 1
	maxS = max(s, maxS)
print(maxS)


N = int(input())
a = [int(x) for x in input().strip().split()]
n = len(a)
(p, s) = (sum(a), 0)
for i in range(0, n):
	s += a[i] * (i + 1)
answer = s
for i in range(n - 1, -1, -1):
	s = s - a[i] * n + p
	answer = max(answer, s)
print(answer)


N = int(input())
a = [int(c) for c in input().split()[:N]]
pmean = 0
sum = 0
for i in range(N):
	pmean += (i + 1) * a[i % N]
	sum += a[i]
max_pmean = pmean
for i in range(N - 1):
	pmean = pmean - sum + N * a[i]
	if pmean > max_pmean:
		max_pmean = pmean
print(max_pmean)


N = int(input())
belt = [x for x in map(int, input().split())]
n_sum = sum(belt)
w_sum = sum((belt[i] * (i + 1) for i in range(N)))
max_w_sum = w_sum
for i in belt:
	w_sum = w_sum - n_sum + i * N
	if w_sum > max_w_sum:
		max_w_sum = w_sum
print(max_w_sum)


def rotate(belt):
	belt.insert(0, belt.pop())
	return belt

def pmean(belt, belt_sum, last=None):
	if not last:
		return sum(((i + 1) * v for (i, v) in enumerate(belt)))
	else:
		return last + belt_sum - len(belt) * belt[0]
N = int(input())
belt = list(map(int, input().split()))
belt_sum = sum(belt)
max_pmean = pmean(belt, belt_sum)
last_pmean = max_pmean
for _ in range(N):
	last_pmean = pmean(rotate(belt), belt_sum, last_pmean)
	if last_pmean > max_pmean:
		max_pmean = last_pmean
print(max_pmean)


n = int(input())
arr = list(map(int, input().split()))
arrsum = 0
sum = 0
for i in range(len(arr)):
	sum += (i + 1) * arr[i]
	arrsum += arr[i]
maxsum = sum
for i in range(len(arr)):
	sum = sum - arrsum + n * arr[i]
	maxsum = max(maxsum, sum)
print(maxsum)


def maxpmean(items):
	sumOfItems = 0
	pmeanOfItems = 0
	length = len(items)
	for i in range(0, length):
		item = items[i]
		sumOfItems += item
		pmeanOfItems += item * (i + 1)
	maximum = None
	for i in range(0, length):
		if maximum == None or pmeanOfItems > maximum:
			maximum = pmeanOfItems
		item = items[i]
		pmeanOfItems -= sumOfItems
		pmeanOfItems += item * length
	return maximum
input()
items = [int(x) for x in input().split()]
print(maxpmean(items))


N = int(input())
l = list(map(int, input().split()))
s = sum(l)
pmeanMax = 0
for i in range(N):
	pmeanMax += (i + 1) * l[i]
pmean = pmeanMax
for i in range(1, N):
	pmean -= s
	pmean += N * l[(i + N - 1) % N]
	pmeanMax = max(pmeanMax, pmean)
print(pmeanMax)


n = int(input())
arr = [int(val) for val in input().split()]
shiftDiff = sum(arr)
curr = sum([arr[i] * (i + 1) for i in range(n)])
record = curr
for i in range(n - 1):
	curr = curr - shiftDiff + n * arr[i]
	record = max(curr, record)
print(record)


from sys import stdin

def calculate_pmean(arr):
	pmean = 0
	for (i, a) in enumerate(arr):
		pmean += (i + 1) * a
	return pmean

def max_pmean(arr):
	s = sum(arr)
	pmean = calculate_pmean(arr)
	max_pmean = pmean
	for i in range(1, len(arr)):
		pmean = pmean - s + len(arr) * arr[i - 1]
		max_pmean = max(max_pmean, pmean)
	return max_pmean
n = int(stdin.readline())
arr = [int(x) for x in stdin.readline().split()]
print(max_pmean(arr))


n = eval(input())
a = list(map(int, input().split()))
p = sum([a[i] * (i + 1) for i in range(n)])
mp = p
s = sum(a)
for i in range(n):
	if p > mp:
		mp = p
	p += n * a[i]
	p -= s
print(mp)


from collections import deque

def max_pmean(l):
	n = len(l)
	total = sum(l)
	mx = 0
	for i in range(n):
		mx += (i + 1) * l[i]
	cur = mx
	for i in range(n - 1):
		l.append(l.popleft())
		cur = cur - total + n * l[-1]
		if cur > mx:
			mx = cur
	return mx
n = int(input())
l = deque([int(x) for x in input().strip().split()])
assert n == len(l)
print(max_pmean(l))


pmean = 0
sum_ = 0
N = int(input(''))
lst = input('').split()
for i in range(len(lst)):
	lst[i] = int(lst[i])
	pmean += (i + 1) * lst[i]
sum_ = sum(lst)
temp = pmean
for i in range(len(lst)):
	temp -= sum_
	temp += lst[i] * N
	if temp > pmean:
		pmean = temp
print(pmean)


def max_pmean(arr):
	unweighted_sum = 0
	pmean = 0
	for (i, x) in enumerate(arr):
		unweighted_sum += x
		pmean += (i + 1) * x
	best = pmean
	for i in range(len(arr) - 1):
		pmean = pmean - unweighted_sum + len(arr) * arr[i]
		if best < pmean:
			best = pmean
	return best
N = int(input())
arr = tuple((int(n) for n in input().strip().split()))
ans = max_pmean(arr)
print(ans)


n = eval(input())
maxx = 0
cur = 0
sm = 0
x = ('[' + input() + ']').replace(' ', ',')
a = eval(x)
for i in range(n):
	cur += (i + 1) * a[i]
	sm += a[i]
maxx = cur
for i in range(n):
	cur = cur - sm + n * a[i]
	if cur > maxx:
		maxx = cur
print(maxx)


N = int(input())
conveyor = [int(x) for x in input().split()]
c_shift = sum(conveyor)
best = 0
for i in range(N):
	best += (i + 1) * conveyor[i]
current = best
for p_last in conveyor[::-1]:
	current -= N * p_last
	current += c_shift
	best = max(best, current)
print(best)


n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
cur_val = ans = sum((a[i] * (i + 1) for i in range(n)))
for i in range(n):
	cur_val = cur_val - sum_a + a[i] * n
	ans = max(ans, cur_val)
print(ans)


def rl(T=str):
	return list(map(T, input().split()))
(n,) = rl(int)
v = rl(int)
a = [0] * (n * 2)
for i in range(n * 2 - 1):
	a[i] = v[i % n]
s = [0] * (n * 2)
t = [0] * (n * 2)
for i in reversed(range(n * 2 - 1)):
	s[i] = s[i + 1] + a[i]
	t[i] = t[i + 1] + a[i] * (i + 1)
best = None
for i in range(n):
	sub = t[i] - t[i + n] - (s[i] - s[i + n]) * i
	if best is None or sub > best:
		best = sub
print(best)


n = int(input())
arr = [int(i) for i in str(input()).split()]
n_i = 0
base = 0
ans = 0
for i in range(n):
	x = arr[i]
	n_i += x * (i + 1)
	base += x
ans = n_i
for i in range(n):
	n_i -= base
	n_i += arr[i] * n
	if n_i > ans:
		ans = n_i
print(ans)


(size, arr) = (int(input()), list(map(int, input().split())))
current_sum = sum([arr[i] * (i + 1) for i in range(size)])
(list_sum, max_sum) = (sum(arr), current_sum)
for i in range(0, size):
	current_sum += arr[i] * size - list_sum
	if current_sum > max_sum:
		max_sum = current_sum
print(max_sum)


cur = int(input())
g = []

def cursor(cur, array):
	global g
	lenu = len(array)
	c = cur % lenu
	a = 0
	for i in range(lenu):
		ca = (c + i) % lenu
		a += array[ca] * (i + 1)
	return a
array = [int(i) for i in input().split()]
setp = cursor(0, array)
somme = sum(array)
m = setp
for i in range(1, len(array)):
	setp = setp - somme + array[i - 1] * len(array)
	if setp > m:
		m = setp
print(m)


def computePMEAN(array):
	tmp = 0
	for i in range(len(array)):
		tmp += (i + 1) * array[i]
	return tmp
N = input()
array = [int(i) for i in input().split()]
pMax = computePMEAN(array)
pTmp = pMax
length = len(array)
t = sum(array)
for i in range(1, length):
	indice = length - i
	pTmp = pTmp + t - array[indice] * length
	if pTmp > pMax:
		pMax = pTmp
print(pMax)


from sys import stdin
from collections import deque

def main():
	N = int(stdin.readline())
	A = deque(map(int, stdin.readline().strip().split()))
	return compute_max_pmean(A, N)

def compute_max_pmean(A, N):
	sum_A = sum(A)
	max_pmean = compute_pmean(A, N)
	pmean = compute_pmean(A, N)
	for i in range(N):
		pmean = pmean + N * A[i] - sum_A
		if pmean > max_pmean:
			max_pmean = pmean
	return max_pmean

def compute_pmean(A, N):
	pmean = 0
	for i in range(N):
		pmean += (i + 1) * A[i]
	return pmean
print(main())


def max_conveyor_sum(lst):
	if not lst:
		return 0
	sa = sum(lst)
	smax = sum(((i + 1) * el for (i, el) in enumerate(lst)))
	n = len(lst)
	sprev = smax
	while n > 0:
		scurr = sprev - sa + len(lst) * lst[len(lst) - n]
		if scurr > smax:
			smax = scurr
		sprev = scurr
		n -= 1
	return smax
_ = input()
nums = [int(n) for n in input().strip().split()]
print(max_conveyor_sum(nums))


n = int(input())
a1 = list(map(int, input().split()))
s = sum(a1)
ls = 0
for (i, e) in enumerate(a1):
	ls += (i + 1) * e
ms = ls
for i in range(n):
	ls = ls + s - n * a1[n - i - 1]
	ms = max(ms, ls)
print(ms)


input()
a = list(map(int, input().split()))
n = len(a)
s = sum(a)
p = [sum(((i + 1) * a[i] for i in range(n)))]
for i in range(n - 1):
	p.append(p[i] + n * a[i] - s)
print(max(p))


def main():
	N = int(input())
	line = input().split()
	belt = []
	for i in line:
		belt.append(int(i))
	pmen = 0
	for i in range(N):
		pmen += (i + 1) * belt[i]
	pmenList = [pmen]
	sm = sum(belt)
	for i in range(N - 1):
		pmen = pmenList[len(pmenList) - 1] - sm + belt[i] * N
		pmenList.append(pmen)
	print(max(pmenList))
main()


n = int(input())
A = [int(s) for s in input().split()]
sumOfA = sum(A)
pmeans = [0 for x in range(n)]
pmean = 0
for i in range(n):
	pmean += (i + 1) * A[i]
pmeans[0] = pmean
for i in range(1, n):
	pmeans[i] = pmeans[i - 1] - sumOfA + n * A[i - 1]
print(max(pmeans))


n = int(input())
l = list(map(int, input().split()))
l = [0] + l + l
s = [0]
for i in range(1, 2 * n + 1):
	s.append(s[i - 1] + l[i])
w = 0
for i in range(1, n + 1):
	w += i * l[i]
res = w
for i in range(2, n + 1):
	w += n * l[i + n - 1] - s[i + n - 2] + s[i - 1] - l[i - 1]
	res = max(res, w)
print(res)


N = int(input())
A = list(map(int, input().split()))
S = sum(A)
P = sum((A[i] * (i + 1) for i in range(N)))
cur = P
for i in range(1, N):
	cur += S - N * A[N - i]
	P = max(P, cur)
print(P)


def main():
	input()
	nums = list(map(int, input().split()))
	length = len(nums)
	total = sum(nums)
	peman = 0
	maximum = -9999999999999999999
	for (i, x) in enumerate(nums, 1):
		peman += i * x
	for x in nums:
		peman = peman - total + x * length
		if peman > maximum:
			maximum = peman
	print(maximum)
main()


import sys
n = int(sys.stdin.readline().strip())
ints = [int(x) for x in sys.stdin.readline().strip().split(' ')]
total = 0
pmean = 0
for i in range(n):
	total += ints[i]
	pmean += (i + 1) * ints[i]
max_pmean = pmean
for i in range(n - 1):
	pmean += total
	pmean -= ints[n - 1 - i] * n
	max_pmean = max(pmean, max_pmean)
print(max_pmean)


import sys
DEV = True
DEV = False

def Inc(Max_, Start_=0, Increment_=1):
	for num in range(Start_, Max_, Increment_):
		yield num

def Dec(Max_, Start_=-1, Increment_=-1):
	Max_ -= 1
	it = Inc(Start_, Max_, Increment_)
	return it

def Keys(Dict_, Sort_=True):
	dict_it = Dict_.keys()
	if Sort_:
		dict_it = sorted(dict_it)
	return dict_it

def Print_ra(Ra_):
	out_str = ''
	for entry in Ra_[:-1]:
		out_str += '{0} '.format(str(entry))
	out_str += str(Ra_[-1])
	print(out_str)

def File_open(Dev_, Name_):
	if Dev_:
		return open(Name_, 'r')
	else:
		return None

def File_close(File_):
	if File_ != None:
		File_.close

def Read_int(File_):
	if File_ == None:
		return int(input().strip())
	return int(File_.readline().strip())

def Read_ra(File_, Cast_func_):
	if File_ == None:
		return [Cast_func_(i) for i in input().strip().split()]
	return [Cast_func_(i) for i in File_.readline().strip().split()]

def Gen_rotation(Ra_, Start_idx_):
	rotated_idx = 0
	for entry in Ra_[Start_idx_:]:
		rotated_idx += 1
		yield (entry * rotated_idx)
	for entry in Ra_[:Start_idx_]:
		rotated_idx += 1
		yield (entry * rotated_idx)
f = File_open(DEV, 'test_data.txt')
N = Read_int(f)
ra = Read_ra(f, int)
ra_sum = sum(ra)
best_rotation = 0
for (idx, num) in enumerate(ra):
	best_rotation += (idx + 1) * num
prev_rotation = best_rotation
for rotation_idx in Inc(N, 1):
	rotation = prev_rotation - ra_sum + N * ra[rotation_idx - 1]
	if rotation > best_rotation:
		best_rotation = rotation
	prev_rotation = rotation
print(best_rotation)
File_close(f)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


def f(A):
	s = sum(A)
	pm = 0
	for i in range(len(A)):
		pm += (i + 1) * A[i]
	mx = pm
	for i in range(len(A)):
		pm = pm - s + len(A) * A[i]
		if mx < pm:
			mx = pm
	return mx
input()
print(f([int(i) for i in input().split()]))


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


n = int(input())
nums = [int(i) for i in input().split()]
tot = 0
for i in range(n):
	tot += nums[i] * (i + 1)
maxi = tot
s = sum(nums)
for i in range(n - 1):
	tot = tot - s + n * nums[i]
	if maxi < tot:
		maxi = tot
print(maxi)


prod = 0
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
	prod += a[i] * (i + 1)
max_prod = prod
sigma = sum(a)
for i in range(n):
	prod += sigma
	prod -= a[-1 - i] * n
	if prod > max_prod:
		max_prod = prod
print(max_prod)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
a = [int(item) for item in input().strip().split()]
res = 0
suma = sum(a)
for i in range(n):
	res += a[i] * (i + 1)
mysum = res
for i in range(0, n - 1):
	mysum += -suma + n * a[i]
	if mysum > res:
		res = mysum
print(res)


__author__ = 'danielbaeck'
(n, p) = (int(input()), [int(i) for i in input().split()])
s = sum(p)
pmax = ws = sum((i * (k + 1) for (k, i) in enumerate(p)))
for i in range(n):
	ws += s
	ws -= p[n - 1 - i] * n
	pmax = max(ws, pmax)
print(pmax)


N = int(input())
A = list(map(int, input().split()))
total = sum(A)
last = sum(((i + 1) * e for (i, e) in enumerate(A)))
best = last
for offset in range(len(A)):
	new = last - total + A[offset] * N
	best = max(best, new)
	last = new
print(best)


n = int(input())
a = list(map(int, input().split()))
max_balanced_sum = cur_balanced_sum = sum([(i + 1) * a[i] for i in range(n)])
simple_sum = sum(a)
for i in range(n):
	cur_balanced_sum += n * a[i] - simple_sum
	max_balanced_sum = max(max_balanced_sum, cur_balanced_sum)
print(max_balanced_sum)


n = int(input().strip())
a = list(map(int, input().strip().split()))
plain_total = sum(a)
co = range(1, n + 1)
from operator import mul
c_max = sum(map(mul, a, co))
total = c_max
for i in range(n):
	total -= plain_total
	total += a[i] * n
	if total > c_max:
		c_max = total
print(c_max)


T = int(input().strip())
arr = [int(i) for i in input().strip().split()]
sum_arr = 0
result = 0
maxv = 0
for v in arr:
	sum_arr += v
for i in range(1, T + 1):
	result += arr[i - 1] * i
maxv = result
for v in arr[:-1]:
	result = result - sum_arr + T * v
	if result > maxv:
		maxv = result
print(maxv)


def highest_pmean(a):
	total = sum(a)
	pmean = sum([(i + 1) * v for (i, v) in enumerate(a)])
	best = pmean
	for i in range(len(a)):
		pmean -= total
		pmean += len(a) * a[i]
		if pmean > best:
			best = pmean
	return best
input()
a = list(map(int, input().strip().split()))
print(highest_pmean(a))


import sys

def pmean(lst):
	s = 0
	for (i, v) in enumerate(lst):
		s += (i + 1) * v
	return s
n = int(sys.stdin.readline())
lst = [int(i) for i in sys.stdin.readline().split()]
l_pmean = 0
r_pmean = pmean(lst)
l_sum = 0
r_sum = sum(lst)
max_pmean = r_pmean
for i in range(n - 1):
	last = lst[n - 1 - i]
	r_pmean += r_sum - last * (n + 1)
	l_pmean += l_sum + last
	r_sum -= last
	l_sum += last
	new_pmean = l_pmean + r_pmean
	if new_pmean > max_pmean:
		max_pmean = new_pmean
print(max_pmean)


def main():
	n = int(input())
	nums = [int(x) for x in str(input()).split()]
	total = sum(nums)
	prev_pmean = sum([(x + 1) * y for (x, y) in zip(range(n), nums)])
	max_pmean = prev_pmean
	for i in range(n):
		prev_pmean = prev_pmean - total + nums[i] * n
		if prev_pmean > max_pmean:
			max_pmean = prev_pmean
	print(max_pmean)
main()


from collections import deque
length = int(input())
array = [int(i) for i in input().split()]
psum = sum(array)

def pmean(array):
	psum = 0
	for i in range(len(array)):
		psum += (i + 1) * array[i]
	return psum
temp = currentp = maxp = pmean(array)
rotations = 0
while rotations < length:
	temp -= psum - array[rotations]
	temp += array[rotations] * (length - 1)
	currentp = temp
	if temp > maxp:
		maxp = temp
	rotations += 1
print(maxp)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


N = int(input())
A = [int(x) for x in input().split()]
total_sum = sum(A)
tmp = 0
for (index, a) in enumerate(A, 1):
	tmp += index * a
max_value = tmp
for i in range(1, N):
	tmp = tmp - total_sum + N * A[i - 1]
	max_value = max(tmp, max_value)
print(max_value)


n = int(input())
l = [int(i) for i in input().split()]
s = sum(l)
temp = [0]
for i in range(n):
	temp[0] += (i + 1) * l[i]
for i in range(0, n - 1):
	temp.append(temp[-1] - s + n * l[i])
print(max(temp))


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


n = int(input())
array = list(map(int, input().split()))
total = sum(array)
p_mean = sum(((i + 1) * array[i] for i in range(n)))
best = p_mean
for item in array:
	p_mean += n * item - total
	if p_mean > best:
		best = p_mean
print(best)


from sys import stdin
stdin.readline()
l = [int(x) for x in stdin.readline().split()]
s = sum(l)
m = 0
for (j, v) in enumerate(l):
	m += (j + 1) * v
newm = m
for v in reversed(l[1:]):
	newm = newm + s - len(l) * v
	m = max(m, newm)
print(m)


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


from functools import reduce
n = int(input())
arr = [int(i) for i in input().split()]
s = sum(arr)
result = act_result = sum([elem * (i + 1) for (i, elem) in enumerate(arr)])
for k in arr:
	act_result = act_result - s + k * n
	result = max(result, act_result)
print(result)


t = int(input())
a = [int(x) for x in input().split()]
s = sum(a)
p = 0
for i in range(t):
	p += (i + 1) * a[i]
m = p
for i in range(t):
	p = p - s + t * a[i]
	if p > m:
		m = p
print(m)


from itertools import accumulate
from functools import reduce

def do(a):
	la = len(a)
	tot = sum(a)
	r = reduce(lambda x, y: x + y[0] * y[1], list(enumerate(a, 1)), 0)
	mr = -10 ** 18
	for v in a:
		r += v * len(a) - tot
		mr = max(r, mr)
	return mr
_ = int(input().strip())
a = list((int(i) for i in input().strip().split()))
print(do(a))


T = int(input())
i = input().split(' ')
total = 0
base = 0
max = 0
curr = 0
for l in range(0, T):
	i[l] = int(i[l])
	total = total + i[l]
	base = base + (l + 1) * i[l]
max = base
curr = base
for l in range(1, T):
	curr = curr + total - T * i[T - l]
	if curr > max:
		max = curr
print(max)


import sys

def solve(aa):
	(sm, ism) = (0, 0)
	for (i, a) in enumerate(aa):
		sm += a
		ism += (i + 1) * a
	mx = ism
	for (i, a) in enumerate(aa):
		ism -= sm
		ism += len(aa) * aa[i]
		mx = max(mx, ism)
	return mx
_ = int(input())
aa = list(map(int, input().split()))
print(solve(aa))


import sys
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
max_product = product = sum(((i + 1) * a for (i, a) in enumerate(A)))
total = sum(A)
for i in range(N):
	product += total - N * A[-i - 1]
	max_product = max(max_product, product)
print(max_product)


n = int(input())
arr = [int(x) for x in input().strip().split(' ')]
cur_sum = sum([x * y for (x, y) in zip(arr, range(1, n + 1))])
max_sum = cur_sum
sum_modifier = sum(arr)
sum_modifiers = reversed([sum_modifier - n * arr[i] for i in range(1, n)])
for modifier in sum_modifiers:
	cur_sum += modifier
	if cur_sum > max_sum:
		max_sum = cur_sum
print(max_sum)


N = int(input())
A = list(map(int, input().split()))
B = sum(((i + 1) * a for (i, a) in enumerate(A)))
S = sum(A)
mx = B
for a in A:
	B = B - S + len(A) * a
	if B > mx:
		mx = B
print(mx)


n = int(input())
a = list(map(int, input().split()))
s = sum(a)
ans = 0
for i in range(n):
	ans += (i + 1) * a[i]
mx = float('-inf')
for i in range(n):
	ans -= s
	ans += n * a[i]
	mx = max(mx, ans)
print(mx)


from itertools import accumulate
print((lambda n, ar: sum(map(int.__mul__, range(1, n + 1), ar)) + max((lambda k: accumulate(map(lambda x: n * x - k, ar)))(sum(ar))))(int(input()), tuple(map(int, input().split()))))


import itertools

def main():
	n = int(input())
	a = list(map(int, input().split()))
	s = sum(a)
	t = sum((k * i for (k, i) in enumerate(a, 1)))

	def rot(p, i):
		return p + n * i - s
	a[0] = rot(0, a[0])
	print(t + max(itertools.accumulate(a, rot)))
main()


N = int(input())
v = list(map(int, input().split()))
bsum = 0
sall = sum(v)
for i in range(N):
	bsum += (i + 1) * v[i]
csum = bsum
Mind = 0
Msum = -10 ** 18
for i in range(N):
	bsum += sall
	bsum -= N * v[N - i - 1]
	if bsum > Msum:
		Msum = bsum
		Mind = i
print(Msum)


n = int(input())
a = [int(x) for x in input().split()]
tot = sum(a)
s = sum([a * i for (a, i) in zip(a, range(1, n + 1))])
maxs = s
for x in a:
	s = s - tot + x * n
	maxs = max(s, maxs)
print(maxs)


import sys
n = int(input())
A = [int(x) for x in input().strip().split(' ')]
total = 0
for r in range(1, n + 1):
	total += r * A[r - 1]
sumA = sum(A)
pmean = total
for k in range(n):
	delta = sumA - n * A[n - k - 1]
	total += delta
	if pmean < total:
		pmean = total
print(pmean)


n = int(input())
a = [int(item) for item in input().split()]
sum = 0
s = 0
for i in range(n):
	sum += (i + 1) * a[i]
	s += a[i]
x = sum
for i in range(n - 1, 0, -1):
	x += s - n * a[i]
	if x > sum:
		sum = x
print(sum)


N = int(input())
A = [int(s) for s in input().split()]
best = pmean = sum((i * v for (i, v) in enumerate(A, 1)))
S = sum(A)
for v in reversed(A):
	pmean += S - N * v
	best = max(best, pmean)
print(best)


n = int(input())
a = [int(x) for x in input().split()]
res = []
basic = sum(a)
pmean = 0
for i in range(len(a)):
	pmean += a[i] * (i + 1)
res.append(pmean)
temp = pmean
pmean = 0
for i in range(len(a) - 1):
	pmean = temp - basic + len(a) * a[i]
	res.append(pmean)
	temp = pmean
	pmean = 0
print(max(res))


N = int(input())
A = [int(s) for s in input().split()]
best = pmean = sum((i * v for (i, v) in enumerate(A, 1)))
S = sum(A)
for v in A:
	pmean += N * v - S
	best = max(best, pmean)
print(best)


N = int(input())
A = [int(s) for s in input().split()]
best = pmean = sum((i * v for (i, v) in enumerate(A, 1)))
S = sum(A)
for v in A:
	pmean += N * v - S
	best = max(best, pmean)
print(best)