Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    number = int(input())
    num_list = list(map(int, input().split()))
    sum = 0
    for i in range(number):
        for j in range(i+1, number):
            sum += num_list[i]*num_list[j]
    div = sum // (10**9 + 7)
    print(sum - div * (10**9 + 7))
if __name__ == '__main__':
    main()

### FIXED CODE ###

from sys import stdin
import itertools
def main():
    number = int(input())
    num_list = list(map(int, stdin.readline().split()))
    num_list_sum = sum(num_list)
    total = 0
    for i in range(number):
        num_list_sum -= num_list[i]
        total += num_list[i] * num_list_sum
    print(total % (10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

K = input()
N = len(K)
D = int(input())
X = [0] * D
Y = [0] * D
X[0] = 1
P = 10**9+7
for i in range(N):
    nX = [0] * D
    nY = [0] * D
    for j in range(10):
        for k in range(D):
            nk = (j+k)%D
            nY[nk] += Y[k]
            if j < int(K[i]):
                nY[nk] = (nY[nk] + X[k]) % P
            elif j == int(K[i]):
                nX[nk] = (nX[nk] + X[k]) % P
    
    X, Y = nX, nY
print((X[0] + Y[0] - 1) % P)


### FIXED CODE ###

K = input()
N = len(K)
D = int(input())
Y = [0] * D
P = 10**9+7
a = 0
for i in range(N):
    nY = [0] * D
    c = int(K[i])
    for j in range(10):
        if j < c:
            nk = (j+a) % D
            nY[nk] = (nY[nk] + 1) % P

        for k in range(D):
            nk = (j+k) % D
            nY[nk] = (nY[nk] + Y[k]) % P
        
    a = (a+c) % D
    Y = nY
print((Y[0] - 1 + (a==0)) % P)
### BUGGY CODE ###

import heapq

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [0] * m
c = [0] * m

for i in range(m):
    b[i], c[i] = list(map(int, input().split()))

max_value = max(b)
heapq.heapify(a)

for i in range(m):
    for j in range(b[i] - 1, -1, -1):
        heapq.heappush(a, max(heapq.heappop(a), c[i]))

print(sum(a))


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

for i in range(m):
    bc[i] = list(map(int, input().split()))

a.sort()
bc = sorted(bc, key=lambda x: -x[1])
new = []

cnt = 0

for e in bc:
    new += [e[1]] * e[0]
    cnt += e[0]

    if (n <= cnt):
        break

for i in range(min(n, cnt)):
    a[i] = max(a[i], new[i])

print(sum(a))
### BUGGY CODE ###

def solve():
    MOD = 998244353

    A, B, C, D = map(int, input().split())

    dp = [[0]*(D+1) for _ in range(C+1)]
    dp[A][B] = 1
    for j in range(B+1, D+1):
        dp[A][j] = dp[A][j-1] * A % MOD
    for i in range(A+1, C+1):
        dp[i][B] = dp[i-1][B] * B % MOD

    for i in range(A+1, C+1):
        for j in range(B+1, D+1):
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

    print(dp[C][D])


solve()


### FIXED CODE ###

def solve():
    MOD = 998244353

    A, B, C, D = map(int, input().split())

    dp = [[0]*(D+1) for _ in range(C+1)]
    dp[A][B] = 1
    for j in range(B+1, D+1):
        dp[A][j] = dp[A][j-1] * A % MOD
    for i in range(A+1, C+1):
        dp[i][B] = dp[i-1][B] * B % MOD

    for i in range(A+1, C+1):
        for j in range(B+1, D+1):
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

    print(dp[C][D])


solve()
### BUGGY CODE ###

from math import factorial
import collections
def cmb(n,r):
  if n-r<0:
    return 0
  return factorial(n) // factorial(r) // factorial(n - r)
n=int(input())
a=list(map(int,input().split()))
ccc=[]
for i in range(n):
  ccc.append(cmb(i,2))

c=collections.Counter(a)
for aa in a:
  o=0
  for k,v in c.items():
    if aa==k:
      v-=1
    o+=ccc[v]
  print(o)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
数え=[0]*N
for i in A:
  数え[i-1]+=1
前者=0
for i in 数え:
  前者+=i*(i-1)//2
for i in A:
  後者=数え[i-1]-1
  print(前者-後者)
### BUGGY CODE ###

S=input()
l=len(S)
m=10**9+7
dp=[1]+[0]*12
for i in range(l):
    dp2=[0]*13
    if S[-i-1]=='?':
        for j in range(13):
            for k in range(10):
                dp2[j]+=dp[(j-k*10**i)%13]%m
    else:
        for j in range(13):
            dp2[j]=dp[(j-int(S[-i-1])*10**i)%13]
    dp=dp2
print(dp[5]%m)

### FIXED CODE ###

S=input()[::-1]
l=len(S)
a=1
m=10**9+7
dp=[1]+[0]*12
for d in S:
    dp2=[0]*13
    if d=='?':
        for j in range(13):
            for k in range(10):
                dp2[(j+k*a)%13]+=dp[j]%m
    else:
        for j in range(13):
            dp2[(j+int(d)*a)%13]=dp[j]
    dp=dp2
    a=(a*10)%13 if a!=1 else 10
print(dp[5]%m)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))

m_count = 0
p_count = 0
for A in As:
    if A < 0:
        m_count += 1
    if A > 0:
        p_count += 1

if K <= m_count * p_count:
    l = As[0] * As[-1] - 1
    r = 10000000
elif K > N * (N-1) // 2 - p_count * (p_count-1) // 2 - m_count * (m_count-1) // 2 :
    l = -10000000
    r = max(As[-1] * As[-2], As[0] * As[1])
else:
    print(0)
    exit()

while r - l > 1:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
        if count >= K:
            r = mid
            break
    else:
        l = mid

print(r)



### FIXED CODE ###

from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
As = sorted(map(int, input().split()))
        
l = - (10 ** 18 + 10)
r = 10 ** 18 + 10
while True:
    mid = (l + r) // 2
    count = 0
    for i, A in enumerate(As):
        if A > 0:
            count += bisect_right(As, mid//A, lo = i+1) - (i+1)
        elif A < 0:
            count += N - bisect_left(As, -((-mid)//A), lo = i+1)
        else:
            if mid >= 0:
                count += N - i - 1
    if count < K:
        l = mid
    else:
        r = mid
    if r - l == 1:
        break

print(r)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
a=[0]*3
f=0

for a[0] in range(10):
    for a[1] in range(10):
        for a[2] in range(10):
            #print("pass=",a[0],a[1],a[2])
            f=0
            for ss in s:
                #print(ss,a[f],f)
                if ss == str(a[f]):
                    f+=1
                    if f==3:
                        ans+=1
                        break
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

print(ans)
### BUGGY CODE ###

import sys

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y = map(int,input().split())

MOD = 10**9 + 7

MAX = max(x,y)
MIN = min(x,y)

if (2*MAX - MIN) % 3 != 0 or MAX // MIN > 2:
	print(0)
	sys.exit()

c1 = (2*MAX - MIN) // 3
c2 = MAX - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)


### FIXED CODE ###

import sys

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y = map(int,input().split())

MOD = 10**9 + 7

MAX = max(x,y)
MIN = min(x,y)

if (2*MAX - MIN) % 3 != 0 or MAX / MIN > 2:
	print(0)
	sys.exit()

c1 = (2*MAX - MIN) // 3
c2 = MAX - 2*c1

c1 %= MOD
c2 %= MOD

ans = cmb(c1 + c2 , c1)
print(ans%MOD)
### BUGGY CODE ###

A, B, K = map(int, input().split())

left = A+K-1
right = B-K+1

if left < right:
    for i in range(A, B+1):
        if i <= left or right <= i:
            print(i)
else:
    for i in range(A, B+1):
        print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())
if B-A+1 >= 2*K: # A以上B以下の整数の数が2K以上
    res_list = [i for i in range(A, A+K)] + [i for i in range(B-K+1, B+1)]
else: # A以上B以下の整数の数が2K未満
    res_list = [i for i in range(A, B+1)]
for i in res_list:
    print(i)
### BUGGY CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

import time

S = [int(x) if x!="?" else -1 for x in input()]
# print (S)

# t1 = time.time()

div_num = 1000000007
arr = np.arange(13, dtype = np.uint64)
dp = np.zeros([2, 13], dtype = np.uint64)

# t2 = time.time()

div13_list = [1]
for ii in range(1, len(S)):
    div13_list.append(div13_list[-1] * 10 % 13)

if S[-1] == -1:
    dp[0, :10] = 1
else:
    dp[0, S[-1]] = 1

# t3 = time.time()

for ii in range(1, len(S)):
    ind = -ii-1
    if S[ind] == -1:
        for n in range(10):
            res = (div13_list[ii] * n + arr) % 13
            dp[1, res] += dp[0, arr]
    else:
        res = (div13_list[ii] * S[ind] + arr) % 13
        dp[1, res] += dp[0, arr]
    dp[0] = dp[1] % div_num
    dp[1] = 0

# t4 = time.time()

print (dp[0, 5])


# print (t2-t1)
# print (t3-t2)
# print (t4-t3)


### FIXED CODE ###

import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]

# S = [int(x) if x!="?" else -1 for x in input()]

# print (S)

# div_num = 1000000007
# arr = np.arange(13, dtype = np.uint64)
# # dp = np.zeros([2, 13], dtype = np.uint64)

# div13_list = [1]
# for ii in range(1, len(S)):
#     n = div13_list[-1] * 10 % 13
#     if n in div13_list:
#         break
#     else:
#         div13_list.append(n)
# div13_mat = np.array([div13_list] * 10, dtype = int)
# div13_mat = (div13_mat * np.arange(10)[:, None] % 13).T

# if S[-1] == -1:
#     dp[0, :10] = 1
# else:
#     dp[0, S[-1]] = 1

# for ii in range(1, len(S)):
#     # ind = -ii-1
#     # tmp = div13_mat[ii%6]
#     # if S[ind] == -1:
#     #     for n in range(10):
#     #         res = np.roll(arr, -tmp[n])
#     #         # dp[1, res] += dp[0, arr]
#     # else:
#     #     res = np.roll(arr, -tmp[S[ind]])
#     #     # dp[1, res] += dp[0, arr]
#     dp[0] = dp[1] % div_num
#     dp[1] = 0


# print (dp[0, 5])

#
# 大きい方の桁からやってく方法
#

MOD = 1000000007;

S = [int(x) if x!="?" else -1 for x in input()]
n = len(S)

# r[i]
# 現在考えてる一つ前の桁数で、余りが i になる整数の個数
r = [0] * 13

# まず一つ目の値が１の位とする
s = S[0]
if (s != -1):
    r[s] = 1
else:
    for i in range(10): r[i] = 1

# 桁を進めながら個数をカウント
for i in range(1, n):
    # dp[j]
    # 現在考えている桁(i)を除く、余りが j となる整数の個数
    dp = [0] * 26

    # 桁が一つ上がるので、一つ前の余りが 10 倍になる
    for j in range(13):
        dp[j*10%13] += r[j] % MOD

    # アクセスを高速にするため２倍の長さとる (dp[i] == dp[i + 13])
    dp[13:26] = dp[0:13]

    r = [0]*13

    s = S[i]
    if (s == -1):
        w = sum(dp[4:14])
        for j in range(13):
            r[j] += w
            w += dp[j + 1]-dp[j + 4]
    else:
        for j in range(13):
            r[j] += dp[13-s+j]
print (r[5]%MOD)
### BUGGY CODE ###

k,a,b=map(int,input().split())
n=k
z=10**9+7
q=1
x=2
while n>1:
    if n%2!=0:
        q*=x%z
    x*=x%z
    n//=2
ans=q*x%z

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])%z

    return result%z
ans = ans - cmb(k,a)  - cmb(k,b)
print(ans%z-1)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7


def fac(n,a):
    ans=1
    for i in range(n,n-a,-1):
        ans*=i
        ans%=mod
    return ans%mod

def inv_fac(n):
    ans=pow(fac(n,n-1),mod-2,mod)
    return ans%mod



ans=pow(2,n,mod)-fac(n,a)*inv_fac(a)-fac(n,b)*inv_fac(b)
print(ans%mod-1)
### BUGGY CODE ###

n = int(input())

l = list(map(int, input().split()))

ans = 1

for x in l:
  ans = ans*x
  
if(ans > 1000000000000000000):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

def main():
    n = int(input())
    l = list(map(int, input().split()))
    ans = 1
    
    if 0 in l:
      print(0)
      return
 
    for x in l:
        ans = ans*x
        if(ans > 1000000000000000000):
            print(-1)
            return
    print(ans)
 
main()
### BUGGY CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
s=[set() for i in range(n+1)]
parent_list=set()
for i in range(m):
  a,b=map(int,input().split())
  s[a].add(b)
  s[b].add(a)
  uf.unite(a,b)
for i in range(k):
  c,d=map(int,input().split())
  s[c].add(d)
  s[d].add(c)
for i in range(1,n+1):
  parent_list.add(uf.find(i))
ans=[0]*(n+1)
for i in parent_list:
  l=set(uf.members(i))
  v=uf.size(i)
  for j in l:
    ans[j]-=len(l&s[j])
  for j in l:
    ans[j]+=v-1
print(*ans[1:])

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents=[-1]*n
    def find(self,x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return
        if self.parents[x]>self.parents[y]:
            x,y=y,x
        self.parents[x]+=self.parents[y]
        self.parents[y]=x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    def roots(self):
        return [i for i,x in enumerate(self.parents) if x<0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
n,m,k=map(int,input().split())
uf=UnionFind(n+1)
cnt=[0]*(n+1)
for i in range(m):
  a,b=map(int,input().split())
  uf.unite(a,b)
  cnt[a]+=1
  cnt[b]+=1
for i in range(k):
  c,d=map(int,input().split())
  if uf.same(c,d):
    cnt[c]+=1
    cnt[d]+=1
ans=[]
for i in range(1,n+1):
  ans.append(uf.size(i)-cnt[i]-1)
print(*ans)
### BUGGY CODE ###

n, m = map(int, input().split(' '))
submits = [list(input().split(' ')) for i in range(m)]
acs = set([submit[0] for submit in submits if submit[1]=='AC'])

WA_nums = dict()
ACs = []
penalty = 0
for submit in submits:
    p, s = submit
    if not p in acs:
        continue
    elif p in ACs:
        continue
    if s == 'AC':
        if p in WA_nums:
            penalty += WA_nums[p]
        ACs.append(p)
    else:
        if p in WA_nums:
            WA_nums[p] += 1
        else:
            WA_nums[p] = 1

print(len(acs), penalty)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split(' '))

WAs = [0] * n
correct = 0
penalty = 0
for i in range(m):
    p, s = input().strip().split(' ')
    p = int(p) - 1
    if WAs[p] == -1:
        continue
    if s == 'AC':
        penalty += WAs[p]
        correct += 1
        WAs[p] = -1
    else:
        WAs[p] += 1

print(correct, penalty)
### BUGGY CODE ###

n=int(input())
sum=0
while (n>0):
    sum+=(n%10)
    n//=10
if (sum%9==0):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s=input()
sum=0
for i in range(0,len(s)):
    sum+=(int(s[i]))
if (sum%9==0):
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[-1]*310 for i in range(310)] for j in range(310)]

@lru_cache(maxsize=None)
def bfs(one, two, thr):
    if dp[one][two][thr]!=-1:
        return dp[one][two][thr]
    if one==two==thr==0:
        return 0.0
    tmp=1.0
    if one>0:
        tmp+=bfs(one-1,two,thr)*one/n
    if two>0:
        tmp+=bfs(one+1,two-1,thr)*two/n
    if thr>0:
        tmp+=bfs(one,two+1,thr-1)*thr/n
    
    tmp*=n/(one+two+thr)
    dp[one][two][thr]=tmp
    return tmp

print(bfs(lst[0],lst[1],lst[2]))

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))

lst=[0]*3
for i in range(n):
    lst[a[i]-1]+=1

dp=[[[0.0]*310 for i in range(310)] for j in range(310)]

for k in range(lst[2]+1):
    for j in range(lst[1]+lst[2]+1-k):
        for i in range(lst[0]+lst[1]+lst[2]+1-k-j):
            if i==j==k==0:
                continue
            tmp=1.0
            if i>0:
                tmp+=dp[i-1][j][k]*i/n
            if j>0:
                tmp+=dp[i+1][j-1][k]*j/n
            if k>0:
                tmp+=dp[i][j+1][k-1]*k/n
            
            tmp*=n/(i+j+k)

            dp[i][j][k]=tmp

print(dp[lst[0]][lst[1]][lst[2]])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))

ans = 0
for i in range(N):
    for j in range(i,N):
        if j-i==A[i]+A[j]:
            ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
L = []
for i in range(N):
    L.append(i-A[i])
R = []
for j in range(N):
    R.append(j+A[j])
from collections import Counter
LL = Counter(L)
RR = Counter(R)
ans = 0
for k,v in RR.items():
    ans += v*LL[k]
print(ans)
### BUGGY CODE ###

n, y = map(int, input().split())
ans = []
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if 10000*i + 5000*j + 1000*k == y and i+j+k ==n:
                ans.append([i,j,k])
                break
                
if len(ans) >=1:
    str_ans = map(str, ans[0])
    print(' '.join(str_ans))
if len(ans) == 0:
    print('-1 -1 -1')

### FIXED CODE ###

n, y = map(int, input().split())
ans = []
for i in range(n+1):
    for j in range(n+1-i):
        k = n-i-j
        if 10000*i + 5000*j + 1000*k == y and k >=0:
            ans.append([i,j,k])
            break
                
if len(ans) >=1:
    str_ans = map(str, ans[0])
    print(' '.join(str_ans))
if len(ans) == 0:
    print('-1 -1 -1')
### BUGGY CODE ###

# 解説AC
n = int(input())
A = list(map(int, input().split()))
B = []
for i, e in enumerate(A):
    B.append((e, i + 1))
B.sort(reverse=True)
# dp[i][j]: Aiまで入れた時、左にj個決めた時の最大値
dp = [[-1] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(i + 1):  # 左の個数
        k = i - j  # 右の個数
        ni = i + 1
        val, idx = B[i]
        dp[ni][j] = max(dp[ni][j], dp[i][j] + abs(n - k - idx) * val)
        dp[ni][j + 1] = max(dp[ni][j + 1], dp[i][j] + abs(idx - (j + 1)) * val)
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[n][i])
print(ans)


### FIXED CODE ###

# 解説AC
import sys
input = sys.stdin.buffer.readline

n = int(input())
A = list(map(int, input().split()))
B = []
for i, e in enumerate(A):
    B.append((e, i + 1))
B.sort(reverse=True)
# dp[i][j]: Aiまで入れた時、左にj個決めた時の最大値
dp = [[-1] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(i + 1):  # 左の個数
        k = i - j  # 右の個数
        ni = i + 1
        val, idx = B[i]
        dp[ni][j] = max(dp[ni][j], dp[i][j] + abs(n - k - idx) * val)
        dp[ni][j + 1] = max(dp[ni][j + 1], dp[i][j] + abs(idx - (j + 1)) * val)
ans = 0
for i in range(n + 1):
    ans = max(ans, dp[n][i])
print(ans)
### BUGGY CODE ###

n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
count = 0
for i in a:
    if i > x:
        i = x
        count += i - x
b = a.copy()

count1 = count
for i in range(n-1):
    while a[i] + a[i+1] > x:
        if a[i] > 0:
            a[i] -= 1
        else:
            a[i+1] -= 1
        count1 += 1

count2 = count
for i in range(n-1):
    while b[i] + b[i+1] > x:
        
        if b[i+1] > 0:
            b[i+1] -= 1
        else:
            b[i] -= 1
        count2 += 1

count = min(count1, count2)
print(count)








### FIXED CODE ###

n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

count = 0
previous = 0

for i in a:
    if i + previous > x: 
        excess = i + previous - x
        count += excess
        previous = x - previous
    else: # if not exceeding x.
        previous = i

print(count)