Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math
def combinations(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))


    
n, k = map(int, input().split())
if k == 1:
    print(n - k + 1)
else:    
    for i in range(k):
        print(combinations(n - k + 1, i + 1) * combinations(k - 1, i) % (10 ** 9 + 7))


Fixed submission:
import math
def combinations(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))
    
n, k = map(int, input().split())
if k == 1:
    print(n - k + 1)
else:    
    for i in range(k):
        if n - k < i:
            print("0")
        else:
            print(combinations(n - k + 1, i + 1) * combinations(k - 1, i) % (10 ** 9 + 7))

Buggy python submission (verdict: Runtime Error):
import math
def combinations(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))

n, k = map(int, input().split())
for i in range(k):
    print(combinations(n - k + 1, i + 1) * combinations(k - 1, i) % (10 ** 9 + 7))


Fixed submission:
import math
def combinations(x, y):
    return math.factorial(x) // (math.factorial(x - y) * math.factorial(y))
    
n, k = map(int, input().split())
if k == 1:
    print(n - k + 1)
else:    
    for i in range(k):
        if n - k < i:
            print("0")
        else:
            print(combinations(n - k + 1, i + 1) * combinations(k - 1, i) % (10 ** 9 + 7))
Buggy python submission (verdict: Runtime Error):
cnt = 0
a_sum = []
i = 0
l = 0 
for i in range(n):
    a_sum.append(a[i])
    l += a(i)
    while l >= k:
      	l -= a_sum[0]
        cnt += n - i
        a_sum.pop(0)
        
print(cnt)

Fixed submission:
x, a = map(int, input().split())
print("10") if x >= a else print("0")
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int, input().split())
s = input()
cnt_AC = [0] * (n - 1)

for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        cnt_AC[i] += 1

for i in range(q):
    l, r = map(int, input().split())
    print(sum(cnt_AC[l - 1:r - 1]))
        
    

Fixed submission:
n, q = map(int, input().split())
s = input()
cnt_AC = [0] * n
cnt = 0

for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        cnt += 1
    cnt_AC[i + 1] = cnt

for i in range(q):
    l, r = map(int, input().split())
    print(cnt_AC[r - 1] - cnt_AC[l - 1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

for i in range(1, n):
    for j in range(1, k + 1):
        if j == 1:
            dp[i] = dp[i - j] + abs(h[i] - h[i - j])
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[n - 1])

Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

for i in range(1, n):
    for j in range(1, k + 1):
        if j == 1:
            dp[i] = dp[i - j] + abs(h[i] - h[i - j])
        if i - j >= 0:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))

print(dp[n - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
d, g = map(int, input().split())

lst = [list(map(int, input().split())) for i in range(d)]
#print(lst)

new_lst = [[] for i in range(len(lst))]

for i, j in enumerate(lst):
    #print(i, j)
    for k in range(j[0] + 1):
        new_lst[i].append([k, (k * 100 * (i + 1))])
        if k == j[0]:
            new_lst[i][k][1] += j[1]
        
#print(new_lst)
min_ac = 1000

for i in itertools.product(*new_lst):
    ac = 0
    points = 0
    #print(i)
    for j in range(len(lst)):
        ac += i[j][0]
        points += i[j][1]
    if points >= g:
        if ac <= min_ac:
            min_ac = ac

print(min_ac)

Fixed submission:
d, g = map(int, input().split())
pc = [list(map(int, input().split())) for i in range(d)]

min_ac1 = 1000
min_ac2 = 1000
for i in range(2 ** d):
    points = 0
    ac = 0
    for j in range(d):
        if ((i >> j) & 1) == 1:
            points += pc[j][0] * 100 * (j + 1) + pc[j][1]
            ac += pc[j][0]
    if points < g:
        l = "{:010b}".format(i)
        l = l[10-d:]
        for k in range(d):
            if l[k] == "0":
                tmp = k
                break
        tmp = -(tmp - d)
        if (g - points + tmp * 100 - 1) // (tmp * 100) < pc[tmp - 1][0]:
            tmp_ac = ac + (g - points + tmp * 100 - 1) // (tmp * 100)
            if tmp_ac < min_ac1:
                min_ac1 = tmp_ac
    if points >= g:
        if ac < min_ac2:
            min_ac2 = ac
    #print(bin(i), ac, points, min_ac1, min_ac2)
print(min(min_ac1, min_ac2))
Buggy python submission (verdict: Time Limit Exceeded):
from math import sqrt
n = int(input())
m = int(sqrt(n))
lst = []
for i in range(2, m + 1):
    if n % i == 0:
        j = 0
        while True:
            if n % i == 0:
                n //= i
                j += 1
            else:
                for k in range(j):
                    lst.append(i)
                break

lst.append(n)

ans = float("INF")
for i in range(2 ** len(lst)):
    num1 = 1
    num2 = 1
    for j in range(len(lst)):
        if (i >> j) & 1:
            num1 *= lst[j]
        else:
            num2 *= lst[j]
    ans = min(ans, max(len(str(num1)), len(str(num2))))
    
print(ans)
            
            


Fixed submission:
from math import sqrt
n = int(input())
m = int(sqrt(n))
lst = []
for i in range(2, m + 1):
    if n % i == 0:
        j = 0
        while True:
            if n % i == 0:
                n //= i
                j += 1
            else:
                for k in range(j):
                    lst.append(i)
                break

lst.append(n)

ans = float("INF")
for i in range(2 ** len(lst)):
    num1 = 1
    num2 = 1
    for j in range(len(lst)):
        if (i >> j) & 1:
            num1 *= lst[j]
        else:
            num2 *= lst[j]
    ans = min(ans, max(len(str(num1)), len(str(num2))))
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
k, s = map(int, input().split())

ans = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                ans += 1
                
print(ans)

Fixed submission:
k, s = map(int, input().split())

ans = 0

for x in range(k + 1):
    for y in range(k + 1):
        z = s - (x + y)
        if 0 <= z <= k:
            ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int,input().split()))
ans = 1
ok = True
for i in a:
  ans *= i
  if ans > 1000000000000000000:
    ok = False
  if i == 0:
    print(0)
    exit()
if ok:
  print(ans)
else:
  print(-1)

Fixed submission:
n = int(input())
a = list(map(int,input().split()))
ans = 1
ok = True
for i in a:
  if ok == True:
    ans *= i
  if ans > 1000000000000000000:
    ok = False
  if i == 0:
    print(0)
    exit()
if ok:
  print(ans)
else:
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
import collections
N = int(input())
A = list(map(int,input().split()))
sameNumber = collections.Counter(A)

def count(val):
  cnt = 0
  sameNumber[val] -= 1
  for n in sameNumber:
    cnt += sameNumber[n] * (sameNumber[n]-1) //2
  sameNumber[val] += 1
  return cnt

for n in A:
  res = 0
  res += count(n)
  print(res)

Fixed submission:
import collections
N = int(input())
A = list(map(int,input().split()))
sameNumber = collections.Counter(A)
total = 0
for n in sameNumber:
  total += sameNumber[n] * (sameNumber[n]-1)

def count(val):
  if sameNumber[val] > 1:
    return (total -2 * (sameNumber[val]-1)) //2
  return total //2

for n in A:
  print(count(n))
Buggy python submission (verdict: Time Limit Exceeded):
takahashi, aoki, kurikaeshi = input().split()
t,a = int(takahashi),int(aoki)
for i in range(int(kurikaeshi)):
  if t >= 1:
     t -= 1
  elif a >= 1:
    a -= 1
print(t,a)


Fixed submission:
t,a,k = map(int, input().split())
T = max(t - k,0)
k-=t-T
A = max(a - k,0)
print(T,A)
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
def main(val):
  for i in range(2,math.floor(math.sqrt(val)):
   if val % i == 0:
     return True
  return False
while(True):
  if main(N) == False:
	print(N)
	break
  N += 1

Fixed submission:
import math
N = int(input())
def main(val):
  for i in range(2,int(math.sqrt(val))):
    if val % i == 0:
      return True
  return False
while(True):
  if main(N) == False:
    print(N)
    break
  N += 1
Buggy python submission (verdict: Runtime Error):
num=int(input())
strs=input().split()
for i in range(num):
  strs[1].insert(i,strs[0][i])
print(strs[1])

Fixed submission:
num=int(input())
strs=input().split()
text=""
for i in range(num):
  text+=strs[0][i]
  text+=strs[1][i]
print(text)
Buggy python submission (verdict: Runtime Error):
import math
a,b=map(int,input().split())
print((a*b)//math.gcd(a,b))

Fixed submission:
import fractions
a,b=map(int,input().split())
print((a*b)//fractions.gcd(a,b))
Buggy python submission (verdict: Runtime Error):
x,y = input().split()
x = chr(x)
y = chr(y)
if x > y:
  print(">")
elif x < y:
  print("<")
else:
  print("=")

Fixed submission:
x,y = input().split()
a = ord(x)
b = ord(y)
if a < b:
  print("<")
elif a > b:
  print(">")
else:
  print("=")
Buggy python submission (verdict: Time Limit Exceeded):
h,w = map(int,input().split())
if h % 3 == 0 or w % 3 == 0:
  print(0)
  exit()
ans = 1000000000
for change in range(2): #heightとwidthを入れ替えてもう一回実行する
  for ox in range(1,w):
    if not ox == w - 1:
      for tx in range(ox+1, w):
        ans = min(ans, h * (max(ox, tx-ox, w-tx) - min(ox, tx-ox, w-tx)))
    for ty in range(1, h):
      ans = min(ans, max(ty*w, ox*(h-ty), (w-ox)*(h-ty)) - min(ty*w, ox*(h-ty), (w-ox)*(h-ty)))
  temp = h
  h = w
  w = temp
print(ans)

Fixed submission:
h,w = map(int,input().split())
if h % 3 == 0 or w % 3 == 0:
  print(0)
  exit()
ans = 10000000000
for change in range(2): #heightとwidthを入れ替えてもう一回実行する
  #二分割
  for ty in range(1,h):
    ans = min(ans, max(ty*w, int(w/2)*(h-ty), (w-int(w/2))*(h-ty)) - min(ty*w, int(w/2)*(h-ty), (w-int(w/2))*(h-ty)))
  a = round(w/3 + 0.1)
  ans = min(ans, h*(max(a, w-a*2) - min(a, w-a*2)))
  temp = h
  h = w
  w = temp
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k = map(int,input().split())
a,b = list(),list()
for i in range(n):
  temp = list(map(int,input().split()))
  a.append(temp[0])
  b.append(temp[1])
for i in range(n):
  for j in range(n-1, i, -1):
    if a[j] < a[j-1]:
      temp = a[j]
      a[j] = a[j-1]
      a[j-1] = temp
      temp = b[j]
      b[j] = b[j-1]
      b[j-1] = temp
sum = 0
for i in range(n):
  sum += b[i]
  if sum >= k:
    print(a[i])
    exit()

Fixed submission:
n,k = map(int,input().split())
num = [0] * 100000
for i in range(n):
  c,d = map(int,input().split())
  num[c-1] += d
sum = 0
for i in range(100000):
  sum += num[i]
  if sum >= k:
    print(i + 1)
    exit()
Buggy python submission (verdict: Runtime Error):
import math
W,a,b = map(int,input().split())
print(max(abs(a-b)-W),0)

Fixed submission:
W,a,b = map(int,input().split())
print(max(abs(a-b)-W,0))

Buggy python submission (verdict: Runtime Error):
W,a,b = map(int,input().split())
print(max(abs(a-b)-W),0)

Fixed submission:
W,a,b = map(int,input().split())
print(max(abs(a-b)-W,0))
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
res = 1
for i in range(N):
  res *= i+1
print(res%1000000007)

Fixed submission:
N = int(input())
res = 1
for i in range(N):
  res *= i+1
  res %= 1000000007
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
K,S=map(int,input().split())
result = 0
for x in range(K+1):
  Y = min(S - x, K)
  for y in range(Y+1):
    Z = min(S - x - y, K)
    for z in range(Z + 1):
      if x + y + z == S:
        result += 1
print(result)

Fixed submission:
K,S=map(int,input().split())
result = 0
for x in range(K+1):
  Y = min(S - x, K)
  for y in range(Y+1):
    if x + y <= S and S - x - y <= K:
      result += 1
print(result)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A = list(map(int,input().split()))
A = list(set(A))
c = 0
for i in range((N+1)%2, N, 2):
  if not A[c] == i:
    print(0)
    end()
  c += 1
print(2**(c-c%2))

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
A.sort()
if N % 2 == 0:
  for i in range(1,N,2):
    for n in range(2):
      if not A[i + n - 1] == i:
        print(0)
        exit()
  print(2**(N//2)%1000000007)
else:
  for i in range(0,N-1,2):
      for n in range(2):
        if i == 0 and n == 0:
          continue
        if not A[i + n - 1] == i:
          print(0)
          exit()
  print(2**((N-1)//2)%1000000007)
Buggy python submission (verdict: Runtime Error):
a = input()
b = input()
ind = []
for i in range(len(a)-len(b)):
  if a[i] == b[0]:
    ind.append(i)

ans = len(b)
for i in range(len(ind)):
  count = 0
  for j in range(len(b)):
    if a[ind[i]+j]!=b[j]:
      count += 1
  ans = min(ans,count)

print(ans)

Fixed submission:
from math import *

def cin(): # To take limited number of inputs
    return map(int,input().split())

def cins(): # To take space sepreated strings
    return input.split()

def cino(test=False): # To take individual int input (test = False)
    if not test:
        return int(input())
    else: # To take string input (test = True)
        return input()

def cina(): # array input
  return list(map(int,input().split()))

def ssplit(): # multiple string input
    return list(input().split())

def printlist(l): # To print space seperated array
    for i in l:
        print(i,end=" ")

def main():
    a,b,c = cin()
    if a/c <= b:
      print("Yes")
    else:
      print("No")

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
n,k = int(input())
f = []
for _ in range(k):
  x = int(input())
  l = list(map(int,input().split()))
  for i in range(len(l)):
    f.append(l[i])
f = set(f)
print(n-len(f))

Fixed submission:
n,k = map(int,input().split())
f = []
for _ in range(k):
  x = int(input())
  l = list(map(int,input().split()))
  for i in range(len(l)):
    f.append(l[i])
f = set(f)
print(n-len(f))
Buggy python submission (verdict: Runtime Error):
n = int(input())
print((2*(x//11)) + (n%11>0 and n%11<=6) + (n>6))

Fixed submission:
from math import *

def cin(): # To take limited number of inputs
    return map(int,input().split())

def cins(): # To take space sepreated strings
    return input.split()

def cino(test=False): # To take individual int input (test = False)
    if not test:
        return int(input())
    else: # To take string input (test = True)
        return input()

def cina(): # array input
  return list(map(int,input().split()))

def ssplit(): # multiple string input
    return list(input().split())

def printlist(l): # To print space seperated array
    for i in l:
        print(i,end=" ")

def main():
   n = int(input())
   print((2*(n//11)) + (n%11>0 and n%11<=6) + 2*(n%11>6))



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7

ans=1

if K==N:
    for i in range(N):
        ans*=A[i]
        ans%MOD
elif max(A)<0 and K%2==1:
    A.sort(reverse=True)
    for i in range(K):
        ans*=A[i]
        ans%MOD
else:
    Ap=[]
    Am=[]
    
    for i in range(N):
        if A[i]>0:
            Ap.append(A[i])
        else:
            Am.append(A[i])
        

    Ap.sort(reverse=True)
    Am.sort()
    
    if K%2==1:
        ans*=Ap.pop(0)
    
    if len(Ap)%2==1:
        Ap.append(1)
    
    P=[]
    
    for i in range(len(Ap)//2):
        P.append(Ap[i*2]*Ap[i*2+1])
    
    for i in range(len(Am)//2):
        P.append(Am[i*2]*Am[i*2+1])
    
    P.sort(reverse=True)
    
    for i in range(K//2):
        ans*=P[i]
        ans%MOD

print(ans%MOD)

Fixed submission:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))

A.sort()
ans=max(A)

for i in range(N-2):
    ans+=A[-(2+i//2)]

print(ans)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
X,N=map(int,input().split())
P=[]
if N!=0:
    P=list(map(int,input().split()))
K=[]
for i in range(1,101):
    if not(i in P):
        K.append(i)

ans=[]

for i in range(len(K)):
    ans.append([abs(X-K[i]),K[i]])

ans.sort()

print(ans[0][1])


Fixed submission:
# coding: utf-8
X,N=map(int,input().split())
P=[]
if N!=0:
    P=list(map(int,input().split()))
K=[]
for i in range(102):
    if not(i in P):
        K.append(i)

ans=[]

for i in range(len(K)):
    ans.append([abs(X-K[i]),K[i]])

ans.sort()

A=[]

for i in range(len(ans)):
    if ans[i][0]==ans[0][0]:
        A.append(ans[i][1])

print(min(A))
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
from heapq import heappush,heappop

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

for k in range(K):
    tmp1=[0 for i in range(N)]
    tmp2=[0 for i in range(N)]
    
    h1=[]
    h2=[]
    num1=0
    num2=0
    for i in range(N):
        heappush(h1,A[i]+i)
        num1+=1
        tmp1[i]+=num1
        # print("h1",h1[0],i,)
        while h1[0]==i:
            # print("!")
            heappop(h1)
            num1-=1
            if len(h1)==0:
                break
        
        heappush(h2,Ar[i]+i)
        tmp2[i]=num2
        num2+=1
        # print("h2",h2[0],i)
        while h2[0]==i:
            # print("?")
            l=heappop(h2)
            num2-=1
            if len(h2)==0:
                break
    
    for i in range(N):
        A[i]=tmp1[i]+tmp2[-(1+i)]
    Ar=list(reversed(A))
    
    if set(A)==set([N]):
        break
# print(tmp1,tmp2)
# print(h1,h2)
print(*A)

Fixed submission:
# coding: utf-8
import copy
N,K=map(int,input().split())
A=list(map(int,input().split()))
for k in range(K):
    imos=[0 for i in range(N+1)]
    
    for i in range(N):
        imos[max(i-A[i],0)]+=1
        imos[min(i+A[i]+1,N)]-=1
    tmp=[imos[0]]
    for i in range(N-1):
        tmp.append(tmp[i]+imos[i+1])
    A=copy.deepcopy(tmp)
    if set(A)==set([N]):
        break
    
print(*A)
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
A,B=map(int,input().split())
B=B*100

ans=A*B
ans=ans/100

print(ans)

Fixed submission:
# coding: utf-8
A,B=input().split()
A=int(A)
B=int(B.replace('.',""))
ans=A*B
ans=ans//100

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
N,S=map(int,input().split())
A=list(map(int,input().split()))
MOD=998244353

dp=[[0 for j in range(S+1)] for i in range(N+1)]

dp[0][0]=1

for i in range(1,N+1):
    a=A[i-1]
    for j in range(0,S+1):
        dp[i][j]+=dp[i-1][j]*2
        if j-a>=0:
            dp[i][j]+=dp[i-1][j-a]
        dp[i][j]=dp[i][j]%MOD


print(dp[N][S])

Fixed submission:
# coding: utf-8
N,S=map(int,input().split())
A=list(map(int,input().split()))
MOD=998244353

dp=[[0 for j in range(S+1)] for i in range(N+1)]

dp[0][0]=1

for i in range(1,N+1):
    a=A[i-1]
    for j in range(0,S+1):
        dp[i][j]+=dp[i-1][j]*2
        if j-a>=0:
            dp[i][j]+=dp[i-1][j-a]
        dp[i][j]=dp[i][j]%MOD


print(dp[N][S])
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
A,B,N=map(int,input().split())

min_x = 1
max_x = N

def f(x):
    y = (A*x)//B - A*(x//B)
    return y

def tren_isOK(x1,x2):
    if f(x1) >= f(x2):
        return True
    else:
        return False


def treary_search():
    left = min_x
    right = max_x

    while abs(right - left) >10**(-8):
        p1 = (right + 2*left)/3
        p2 = (2*right + left)/3

        if tren_isOK(p1,p2):
            right = p2
        else:
            left = p1
    
    return right

x=treary_search()
ans=max(f(int(x)),f(int(x)+1))
print(ans)

Fixed submission:
# coding: utf-8
A,B,N=map(int,input().split())

min_x = 1
max_x = N

def f(x):
    y = (A*x)//B - A*(x//B)
    return y
    
ans=f(min(B-1,N))
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
A,B,N=map(int,input().split())

min_x = 1
max_x = N

def f(x):
    y = (A*x)//B - A*(x//B)
    return y

def tren_isOK(x1,x2):
    if f(x1) >= f(x2):
        return True
    else:
        return False


def treary_search():
    left = min_x
    right = max_x

    while abs(right - left) >10**(-8):
        p1 = (right + 2*left)/3
        p2 = (2*right + left)/3

        if tren_isOK(p1,p2):
            right = p2
        else:
            left = p1
    
    return right

x=treary_search()
ans=max(f(int(x)),f(int(x)+1))
print(ans)

Fixed submission:
# coding: utf-8
A,B,N=map(int,input().split())

min_x = 1
max_x = N

def f(x):
    y = (A*x)//B - A*(x//B)
    return y
    
ans=f(min(B-1,N))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))
INF=10**9
dp=[[-INF for i in range(N+1)] for j in range(N+1)]
dp[0][0]=0
AI=[]

for i in range(N):
    AI.append([A[i],i+1])
    
AI.sort()
AI.reverse()

for i in range(1,N+1):
    a=AI[i-1][0]
    I=AI[i-1][1]
    for j in range(N+1):
        if j==0:
            dp[i][j]=dp[i-1][j]+abs(I-(N+1-i))*a
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+abs(I-j)*a
        else:
            dp[i][j]=max(dp[i-1][j-1]+abs(I-j)*a,dp[i-1][j]+abs(I-(N+1-(i-j)))*a)
ans=0
for i in range(N+1):
    ans=max(ans,dp[N][i])

print(ans)

Fixed submission:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))
INF=10**9
dp=[[-INF for i in range(N+1)] for j in range(N+1)]
dp[0][0]=0
AI=[]

for i in range(N):
    AI.append([A[i],i+1])
    
AI.sort()
AI.reverse()

for i in range(1,N+1):
    a=AI[i-1][0]
    I=AI[i-1][1]
    for j in range(N+1):
        if j==0:
            dp[i][j]=dp[i-1][j]+abs(I-(N+1-i))*a
        elif j==i:
            dp[i][j]=dp[i-1][j-1]+abs(I-j)*a
        else:
            dp[i][j]=max(dp[i-1][j-1]+abs(I-j)*a,dp[i-1][j]+abs(I-(N+1-(i-j)))*a)
ans=0
for i in range(N+1):
    ans=max(ans,dp[N][i])

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
N=int(input())
S=list(input())
RGB=[[0,0,0] for i in range(N)]

ans=0

for i in range(1,N):
    k=-i
    if S[k]=="R":
        RGB[k-1][0]=RGB[k][0]+1
        RGB[k-1][1]=RGB[k][1]
        RGB[k-1][2]=RGB[k][2]
    elif S[k]=="G":
        RGB[k-1][0]=RGB[k][0]
        RGB[k-1][1]=RGB[k][1]+1
        RGB[k-1][2]=RGB[k][2]
    elif S[k]=="B":
        RGB[k-1][0]=RGB[k][0]
        RGB[k-1][1]=RGB[k][1]
        RGB[k-1][2]=RGB[k][2]+1

for i in range(N):
    for j in range(i,N):
        if S[i]!=S[j]:
            if S[i]=="R" and S[j]=="G" or S[i]=="G" and S[j]=="R":
                ans+=RGB[j][2]
                if 2*j-i<N:
                    if RGB[j][2]>0 and S[2*j-i]=="B":
                        ans-=1
            elif S[i]=="R" and S[j]=="B" or S[i]=="B" and S[j]=="R":
                ans+=RGB[j][1]
                if 2*j-i<N:
                    if RGB[j][1]>0 and S[2*j-i]=="G":
                        ans-=1
            elif S[i]=="B" and S[j]=="G" or S[i]=="G" and S[j]=="B":
                ans+=RGB[j][0]
                if 2*j-i<N:
                    if RGB[j][0]>0 and S[2*j-i]=="R":
                        ans-=1

print(ans)

Fixed submission:
# coding: utf-8
N=int(input())
S=list(input())
RGB=[[0,0,0] for i in range(N)]

ans=0

for i in range(1,N):
    k=-i
    if S[k]=="R":
        RGB[k-1][0]=RGB[k][0]+1
        RGB[k-1][1]=RGB[k][1]
        RGB[k-1][2]=RGB[k][2]
    elif S[k]=="G":
        RGB[k-1][0]=RGB[k][0]
        RGB[k-1][1]=RGB[k][1]+1
        RGB[k-1][2]=RGB[k][2]
    elif S[k]=="B":
        RGB[k-1][0]=RGB[k][0]
        RGB[k-1][1]=RGB[k][1]
        RGB[k-1][2]=RGB[k][2]+1

for i in range(N):
    for j in range(i,N):
        if S[i]!=S[j]:
            if S[i]=="R" and S[j]=="G" or S[i]=="G" and S[j]=="R":
                ans+=RGB[j][2]
                if 2*j-i<N:
                    if RGB[j][2]>0 and S[2*j-i]=="B":
                        ans-=1
            elif S[i]=="R" and S[j]=="B" or S[i]=="B" and S[j]=="R":
                ans+=RGB[j][1]
                if 2*j-i<N:
                    if RGB[j][1]>0 and S[2*j-i]=="G":
                        ans-=1
            elif S[i]=="B" and S[j]=="G" or S[i]=="G" and S[j]=="B":
                ans+=RGB[j][0]
                if 2*j-i<N:
                    if RGB[j][0]>0 and S[2*j-i]=="R":
                        ans-=1

print(ans)