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

import math
K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            ans += math.gcd(math.gcd(a,b),c)
print(ans)
exit()


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
from fractions import gcd
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def gcd(*numbers):
    return functools.reduce(math.gcd, numbers)
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort(reverse=True)
    return divisors

K = _I()

ans = 0
d = {}
vals = []
for i in range(1, K+1):
    for j in range(1, K+1):
        nums = [i,j]
        nums.sort()
        key = str(i) + '-' + str(j)
        if key in d:
            vals.append(d[key])
        else:
            val = gcd(i,j)
            d[key] = val
            vals.append(val)
#  print(vals)
#  print(d)
for val in vals:
    for k in range(1, K+1):
        #  print(val, k)
        nums = [i,j]
        nums.sort()
        key = str(val) + '-' + str(k)
        if key in d:
            ans += d[key]
        else:
            val = gcd(val, k)
            ans += val
            d[key] = val
print(ans)
exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
from bisect import bisect_left

def hantei(n, mid, s, suffix):
    # print(mid, s, suffix)
    tmp = "A" + s[:mid-1]
    for i in range(n - mid + 1):
        # tmp = (s[i:i+mid], i)
        tmp = tmp[1:] + s[i+mid-1]

        idx = bisect_left(suffix, tmp)

        # if mid == 4:
        #     print(tmp, idx)
        flag = True
        while(flag):
            tgt = suffix[idx]
            # print(tgt)
            if tgt.startswith(tmp):
                if int(tgt[-9:]) >= i + mid:
                    return True
                else:
                    idx += 1
                    if idx >= n:
                        flag = False
            else:
                flag = False

n = getN()
s = input().strip()

suffix = []

for i in range(n):
    # suffix.append((s[i:], i))
    suffix.append(s[i:] + "{:0>10}".format(i))

suffix.sort()

mn = 0
mx = n // 2 + 1
while(mx-mn>1):
    mid = (mx + mn) // 2
    is_succ = hantei(n, mid, s, suffix)
    if is_succ:
        mn = mid
    else:
        mx = mid

if hantei(n, mx, s, suffix):
    print(mx)
else:
    print(mn)

"""
17
aaaaaaaaaaaaaaaaa -> 8
10
absoabsoab -> 4
6
abcabc -> 3
10
abcdefghij -> 0
15
rangerangerange -> 5
2
xx -> 1
2
xy -> 0
12
abcdxxxxabcd -> 4

14
abcxxxxxxxxabc
3????????????????
"""

### FIXED CODE ###

import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

dic = dict()

def zalg(s):
    n = len(s)
    ret = [0] * n
    ret[0] = n
    i, j = 1, 0
    while i < n:
        while i + j < n and s[j] == s[i+j]:
            j += 1
        ret[i] = j

        if j == 0:
            i += 1
            continue

        k = 1
        while k < j and k + ret[k] < j:
            ret[i + k] = ret[k]
            k += 1

        i += k
        j -= k

    return ret

def solve(n=None, s1=None, s2=None):
    n = getN()
    s = list(getS())
    ans = 0
    for i in range(n):
        ps = s[i:]
        z = zalg(ps)
        for i, zz in enumerate(z):
            if i >= zz:
                ans = max(ans, zz)
    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()
### BUGGY CODE ###

n = int(input())
import math

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

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


for i in range(n):
    l1 = l[:]
    ans = 0
    l1[a[i] - 1] -= 1
    for j in range(len(l)):
        ans += l1[j] * (l1[j] - 1) / 2
    print(math.floor(ans))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for _ in range(max(a) + 1)]
for x in a:
    b[x] += 1
c = sum([x * (x-1) // 2 for x in b])
for i in range(n):
    print(c -(b[a[i]]-1))
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
x=[0 for i in range(n)]
sum=0
for i in range(n):
    if i%2==0:
        sum=sum+a[i]
    else:
        sum=sum-a[i]

x[0]=sum//2

for i in range(1, n):
    x[i]=a[i-1]-x[i-1]

ans=""
for i in range(n):
    ans=ans+str(x[i]*2)+" "
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
x=[0 for i in range(n)]
sum=0
for i in range(n):
    if i%2==0:
        sum=sum+a[i]
    else:
        sum=sum-a[i]

x[0]=sum//2

for i in range(1, n):
    x[i]=a[i-1]-x[i-1]

x=map(lambda t:t*2, x)
x=map(str, x)

ans=" ".join(x)

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

N=int(input())
Ln=list(map(int,input().split()))
Ln.sort(reverse=True)
Ans=0
 
for i in range(N-2):
    di=i+1
    for j in range(N-di-1):
        dj=di+j+1
        for k in range(N-dj):
            dk=dj+k+1
            a=Ln[di-1]
            b=Ln[dj-1]
            c=Ln[dk-1]
            if((a+b)>c)&((b+c)>a)&((c+a)>b) :
                Ans +=1
 
print(Ans)

### FIXED CODE ###

N=int(input())
Ln=list(map(int,input().split()))
Ln.sort(reverse=True)
Ans=0
left=0
right=0
 
for i in range(N-2):
    di=i+1
    for j in range(N-di-1):
        dj=di+j+1
        A=Ln[di-1]
        B=Ln[dj-1]
        if (B+Ln[dj])<A : break
 
        right=N-1
        left=dj
        while left<=right :
            mid=int((right+left)/2)
            if (B+Ln[mid])>A :
                left=mid+1
            else :
                right=mid-1
        Ans+=(left-1)-(dj-1)
 
print(Ans)
### BUGGY CODE ###

a,b,k = list(map(int, input().split()))

for idx in range(k):
  if (a >= 1):
    a = a - 1
  elif (b >= 1) :
    b = b -1
  else :
    pass

print("%s %s" % (a,b))

### FIXED CODE ###

a,b,k = list(map(int, input().split()))

temp_a = a
if (k >= a):
  a = 0
else :
  a = (a - k)
k = k - temp_a

if k < 0 :
  k = 0
if (k >= b):
  b = 0
else :
  b = (b - k)


print("%s %s" % (a,b))
### BUGGY CODE ###

a, b, x = map(int, input().split())
ans = 0
for i in range(a, b+1):
    if i % x == 0:
        ans += 1
print(ans)


### FIXED CODE ###

a, b, x = map(int, input().split())
if a != 0:
    print(b//x - (a-1)//x)
else:
    print(b//x + 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
counter = n
for i in range(n-1):
	k = i+1
	cumsum = a[i]
	while k <= n-1 and cumsum^a[k] == cumsum+a[k]:
		counter += 1
		cumsum += a[k]
		k += 1
print(counter)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
counter = n
prev = [[0,0]]

total = [0]
for i in range(n):
	total.append(total[i]+a[i])

for i in range(n-1):
	k = prev[i][1]+1
	counter += prev[i][1]-i
	cumsum = total[k]-total[i]
	while k <= n-1 and cumsum^a[k] == cumsum+a[k]:
		counter += 1
		cumsum += a[k]
		k += 1
	prev.append([i,k-1])
print(counter)
### BUGGY CODE ###

from heapq import heappop,heappush

def prim():
    used = [True]*n
    edgelist = []
    for e in edge[0]:
        heappush(edgelist,e)
    used[0] = False
    res = 0
    while len(edgelist) != 0:
        short_edge = heappop(edgelist)
        if not used[short_edge[1]]:
            continue
        v = short_edge[1]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist,e)
        res += short_edge[0]
    return res

n = int(input())
A = [list(map(int,input().split()))+[i] for i in range(n)]
A.append([-10**12,-10**12,-1])
A.append([10**12,10**12,-1])
X = sorted(A)
Y = sorted(A,key = lambda x:x[1])
distance = [[] for i in range(4*n)]
for i in range(1,n+1):
    sx = X[i-1][0]
    sy = Y[i-1][1]
    mx = X[i][0]
    my = Y[i][1]
    lx = X[i+1][0]
    ly = Y[i+1][1]
    nsx = X[i-1][2]
    nsy = Y[i-1][2]
    nmx = X[i][2]
    nmy = Y[i][2]
    nlx = X[i+1][2]
    nly = Y[i+1][2]
    i -= 1
    distance[4*i] = (nsx,nmx,mx-sx)
    distance[4*i+1] = (nmx,nlx,lx-mx)
    distance[4*i+2] = (nsy,nmy,my-sy)
    distance[4*i+3] = (nmy,nly,ly-my)
    
edge = [[] for i in range(n)]
for i in range(4*n):
    x,y,z = distance[i][0],distance[i][1],distance[i][2]
    if x==-1 or y==-1:
        continue
    edge[x].append([z,y])
    edge[y].append([z,x])

print(prim())

### FIXED CODE ###

def main():
    import sys 
    input = sys.stdin.readline
    from heapq import heappop,heappush
    from operator import itemgetter
    
    def prim():
        used = [True]*n
        edgelist = []
        for e in edge[0]:
            heappush(edgelist,e)
        used[0] = False
        res = 0
        while len(edgelist) != 0:
            short_edge = heappop(edgelist)
            if not used[short_edge[1]]:
                continue
            v = short_edge[1]
            used[v] = False
            for e in edge[v]:
                if used[e[1]]:
                    heappush(edgelist,e)
            res += short_edge[0]
        return res

    n = int(input())
    A = [list(map(int,input().split()))+[i] for i in range(n)]
    A.append([-10**12,-10**12,-1])
    A.append([10**12,10**12,-1])
    X = sorted(A)
    Y = sorted(A,key = itemgetter(1))
    edge = [[] for i in range(n)]
    for i in range(1,n+1):
        sx = X[i-1][0]
        sy = Y[i-1][1]
        mx = X[i][0]
        my = Y[i][1]
        lx = X[i+1][0]
        ly = Y[i+1][1]
        nsx = X[i-1][2]
        nsy = Y[i-1][2]
        nmx = X[i][2]
        nmy = Y[i][2]
        nlx = X[i+1][2]
        nly = Y[i+1][2]
        edge[nsx].append((mx-sx,nmx))
        edge[nmx].append((mx-sx,nsx))
        edge[nlx].append((lx-mx,nmx))
        edge[nmx].append((lx-mx,nlx))
        edge[nsy].append((my-sy,nmy))
        edge[nmy].append((my-sy,nsy))
        edge[nly].append((ly-my,nmy))
        edge[nmy].append((ly-my,nly))

    print(prim()) 

if __name__ == '__main__':
    main()
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

ans = 0
for i in range(k):
    if a > 0:
        ans += 1
        a -= 1

    elif b > 0:
        b -= 1

    elif c > 0:
        ans -= 1
        c -= 1
    else:
        break

print(ans)


### FIXED CODE ###

a, b, c, k = map(int, input().split())

ans = 0
if a < k:
    ans = a
else:
    ans = k

minus = k - (a + b)

if minus > 0:
    ans -= minus

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

N, P = list(map(int, input().split()))
S = input()

tot = 0

if P in [2,5]:
  for i in range(1,N+1):
    if int(S[-i]) % P == 0:
      tot += N-i+1
else:
  S_mod = [0] * P
  S_mod[0] = 1 # 0 = 0 mod P
  for i in range(N-1, -1, -1):
    mod = int(S[i:]) % P
    #print(S[i:], mod)
    tot += S_mod[mod]
    S_mod[mod] += 1
print(tot)
    

### FIXED CODE ###

N, P = list(map(int, input().split()))
S = input()
#S = map(int, list())

tot = 0

if P in [2,5]:
  for i in range(1,N+1):
    if int(S[-i]) % P == 0:
      tot += N-i+1
else:
  S_mod = [0] * P
  S_mod[0] = 1 # 0 = 0 mod P
  mod = 0
  mod10 = 10 % P
  mod_power10 = 1
  for i in range(N-1, -1, -1):
    mod = (int(S[i]) % P * mod_power10 + mod % P) % P
    #print(S[i:], mod)
    tot += S_mod[mod]
    S_mod[mod] += 1
    mod_power10 = (mod_power10 * mod10) % P
print(tot)
### BUGGY CODE ###

H, W, D = map(int, input().split())

A = list(range(H*W+1))

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        A[l[j]] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

### FIXED CODE ###

# speed-test
# https://abc089.contest.atcoder.jp/submissions/2206669

h,w,d = map(int,input().split())
 
dic = {}
for i in range(h):
    a = input().split()
    for j in range(w):
        dic[int(a[j])] = (i+1,j+1)
        
q = int(input())
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
    pi,pj = dic[i]; qi,qj = dic[i-d]
    c[i] = c[i-d] + abs(pi-qi) + abs(pj-qj)
    
for i in range(q):
    l,r = map(int,input().split())
    print(c[r]-c[l])
### BUGGY CODE ###

n, k = list(map(int, input().split()))
s = input()

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値（十分に小さい値）

L=1
L2=0
for i in range(n):
    count=0
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1) and count==1 and v==0:
                L2=j
                v+=1
                continue
                
            
        if count==k+1:
            ans=max(ans,j-L)
            L=L2
            break
            
        if s[j]=='E':
            ans=max(ans,j-L)
            print(ans)
            exit()

### FIXED CODE ###

n, k = list(map(int, input().split()))
s = input()

s =str(1)+ s + 'E'   # 終端処理
ans = -1    # 答えの初期値

L=1
count=0
L2=[1]
for i in range(n):
    if i>=1:
        count-=1
    v=0
    for j in range(L,n+2):
        if s[j]==str(0):
            #連続してる所は飛ばす。
            if s[j-1]==str(0):
                continue
                
            else:
                count+=1
                
        #0のあと初めて1が出たらindexを取得
        if s[j]==str(1):
            if s[j-1]==str(0):
                L2.append(j)
                
            
        if count==k+1:
            
            ans=max(ans,j-L2[i])
            #次はｊ+１から始める
            L=j+1
            break
            
        if s[j]=='E':
            ans=max(ans,j-L2[i])
            print(ans)
            exit()
### BUGGY CODE ###

[k,s]=list(map(int,input().split()))
counter=0
for i in range(s+1):
	for j in range(0,s-i+1):
		if i<=k and j<=k and s-i-j<=k:
			counter+=1
print(counter)

### FIXED CODE ###

[k,s]=list(map(int,input().split()))
counter=0
imax=min(s+1,k+1)
for i in range(imax):
	jmax=min(s-i+1,k+1)
	for j in range(0,jmax):
		if i<=k and j<=k and s-i-j<=k:
			counter+=1
print(counter)
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v)
s,t = inm()
s -= 1
t -= 1

reach2 = [ [] for i in range(n) ]
m2done = [ False for i in range(n) ]
reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]

def mark(f):
    x = []
    if not m2done[f]:
        y = []
        for v1 in dst[f]:
            for v2 in dst[v1]:
                y.append(v2)
        reach2[f] = list(set(y))
        m2done[f] = True

    for v2 in reach2[f]:
                for v3 in dst[v2]:
                    if v3 == f:
                        continue
                    x.append(v3)
    reach3[f] = list(set(x))
    m3done[f] = True

dist = [-1] * n
dist[s] = 0
q = deque([(s,0)])
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==t:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)
### BUGGY CODE ###

prime=[0]*100001
prime[0]=1
prime[1]=1
for i in range(0,100001):
  if prime[i]==0:
    cnt=2
    while cnt*i<100001:
      prime[cnt*i]=1
      cnt+=1

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  ans=0
  for j in range(l,r+1):
    if prime[j]==0 and prime[int((j+1)/2)]==0:
      ans+=1
  print(ans)


### FIXED CODE ###

prime=[0]*100001
prime[0]=1
prime[1]=1
prime_ans=[0]*100001
for i in range(0,100001):
  if prime[i]==0:
    cnt=2
    while cnt*i<100001:
      prime[cnt*i]=1
      cnt+=1
ans=0
for i in range(3,100001):
  if prime[i]==0 and prime[int((i+1)/2)]==0:
    ans+=1
  prime_ans[i]=ans

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  res=prime_ans[r]-prime_ans[l-1]
  print(res)
### BUGGY CODE ###

n, a, b = map(int, input().split())
if a > b:
    print(0)
    exit()
elif a == b:
    print(1)
    exit()
elif n == 1 and b - a > 0:
    print(0)
    exit()
elif n == 2:
    print(1)
    exit()
else:
    mid_num = n - 2
    num_num = b - a + 1
    ans = 0
    for i in range(mid_num-1):
        ans += num_num-1
    ans += num_num
    print(ans)


### FIXED CODE ###

n, a, b = map(int, input().split())
if a > b:
    print(0)
    exit()
elif a == b:
    print(1)
    exit()
elif n == 1 and b - a > 0:
    print(0)
    exit()
elif n == 2:
    print(1)
    exit()
else:
    mid_num = n - 2
    num_num = b - a + 1
    ans = 0
    ans += (num_num-1) * (mid_num-1) + num_num
    print(ans)
### BUGGY CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b_c = [list(map(int,input().split())) for i in range(q)]

cc = collections.Counter(a)
c_buf = 0
cc_j_buf = 0
for i in range(q):
  flag = 0
  b = b_c[i][0]
  c = b_c[i][1]
  count = 0
  for j in cc:
    if j == b:
      if c in cc:
        cc[c] = cc[c] + cc[j]
      else:
        cc_j_buf = cc[j]
        flag = 1
      cc[j] = 0
  if flag == 1:
    cc[c] = cc_j_buf
  for j in cc:
    count = count + j*cc[j]
  print(count)

### FIXED CODE ###

import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b_c = [list(map(int,input().split())) for i in range(q)]

summ = sum(a)
cc = collections.Counter(a)
for i in range(q):
  b = b_c[i][0]
  c = b_c[i][1]
  if b in cc:
    buf = cc[b]
    cc[b] = 0
    if c in cc:
      cc[c] = cc[c] + buf
    else:
      cc[c] = buf
    summ = summ - b*buf + c*buf
    print(summ)
  else:
    print(summ)
### BUGGY CODE ###

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

b=[0 for i in range(n)]
res=0
for i in range(n):
    for j in range(n-1):
        if i+1==a[j]:
            res+=1
    b[i]=res
    res=0
for i in range(n):
    print(b[i])

### FIXED CODE ###

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

b=collections.Counter(a)
for i in range(1,n+1):
    print(b[i])
### BUGGY CODE ###

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

count_use = 0
while count_use < m:
    max_a = max(a)
    a[a.index(max_a)] = max_a//2
    count_use += 1

print(sum(a))

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))
heapq.heapify(a)

count_use = 0
while count_use < m:
    max_a = heapq.heappop(a)
    max_a = -1*((-1*max_a)//2)
    #print(max_a)
    heapq.heappush(a, max_a)
    count_use += 1

print((-1)*sum(a))
### BUGGY CODE ###

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for i in range(N+1)]
    for i in range(N):
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+sortedA[i][0]*abs((N-r-1)-sortedA[i][1]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+sortedA[i][0]*abs(l-sortedA[i][1]))
    print(max(dp[N]))

main()


### FIXED CODE ###

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

    # 全探索するとN!なのでN=2000のときO(N^2000)となるので無理
    # DPで解く
    # dp[i][l] = 係数が大きい順にi個左右の端どちらにつめるか決めて、左をl回(右はn-l回)選んだときの指標最大値

    # 降順にAをソート+元のインデックスも保存しておく
    Awithidx = [[a,i] for i,a in enumerate(A)]
    sortedA = sorted(Awithidx, reverse=True)
    # DP
    dp = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        a = sortedA[i][0]
        idx = sortedA[i][1]
        for l in range(i+1):
            r = i-l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l]+a*abs((N-r-1)-idx))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l]+a*abs(l-idx))
    print(max(dp[N]))

main()
### BUGGY CODE ###

n, m = map(int, input().split())
a = [[] for _ in range(n)]
b = []
for i in range(m):
    s, t = map(int, input().split())
    a[s-1].append(t)
    b.append((s, t))
for i in range(n):
    a[i].sort()

for i in range(m):
    s, t = b[i][0], b[i][1]
    u = a[s-1].index(t)+1
    p, q = str(s), str(u)
    lp, lq = len(p), len(q)
    print("0"*(6-lp) + p + "0"*(6-lq) + q)



### FIXED CODE ###

n, m = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(m)]

cities = [[] for _ in range(n)]

for i, (p, y) in enumerate(a):
    cities[p-1].append((y, i))

ans = [None]*m
for p in range(n):
    for j, (y, i) in enumerate(sorted(cities[p])):
        tmp = str(p+1).zfill(6) + str(j+1).zfill(6)
        ans[i] = tmp

print(*ans, sep="\n")
### BUGGY CODE ###

import heapq

N, M = tuple(map(int, input().split()))
A = list(map(int, input().split()))
B, C = [], []
for _ in range(M):
    b, c = tuple(map(int, input().split()))
    B.append(b)
    C.append(c)

heapq.heapify(A)
for b, c in zip(B, C):
    for _ in range(b):
        min_val = A[0]
        if min_val < c:
            heapq.heappop(A)
            heapq.heappush(A, c)
        else:
            break
print(sum(A))

### FIXED CODE ###

import heapq

N, M = tuple(map(int, input().split()))
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    BC.append(tuple(map(int, input().split())))

BC.sort(key=lambda x: x[1], reverse=True)
heapq.heapify(A)
for (b, c) in BC:
    for _ in range(b):
        min_val = A[0]
        if min_val < c:
            heapq.heappop(A)
            heapq.heappush(A, c)
        else:
            break
print(sum(A))