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

N = int(input())
a = list(map(int, input().split()))
a.sort()
i = N - 1
c = 0
while i >= 0:
    i = N -1
    while a[i] % 2 != 0:
        i -= 1
        if i < 0:
            print(c)
            exit()
    max_ = a[i] // 2
    a = list(map(lambda x: x * 3, a))
    a[i] = max_
    c += 1
    a.sort()

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(N):
    while a[i] % 2 == 0:
        a[i] /= 2
        c += 1
print(c)
### BUGGY CODE ###

n = int(input())
s = input()
ans = float("inf")
for i in range(n):
  ans = min(ans, s[:i].count("W")+s[i+1:].count("E"))
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
w = []
c = 0
for i in range(n):
  if s[i] == "W":
    c += 1
  w.append(c)
e = [i+1-w[i] for i in range(n)]
ans = e[-1]
for i in range(1,n):
  ans = min(ans, w[i-1]+e[-1]-e[i])
print(ans)
### BUGGY CODE ###

import sys
from collections import defaultdict

graph = defaultdict(list)

n, m = map(int, sys.stdin.readline().split())

if m == 0:
    print(1)
    exit()

for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())

    if not b in graph[a]:
        graph[a].append(b)
    if not a in graph[b]:
        graph[b].append(a)

visited = set()
maxi = 0

def dfs(start):
    stk = [start]
    visited.add(start)
    temp = 1

    while stk:
        cur = stk.pop()

        for c in graph[cur]:
            if not c in visited:
                visited.add(c)
                stk.append(c)
                temp += 1

    return temp

for j in graph:
    if not j in visited:
        cnt = dfs(j)
        maxi = max(cnt, maxi)

print(maxi)

### FIXED CODE ###

import sys
from collections import defaultdict

graph = defaultdict(set)

n, m = map(int, sys.stdin.readline().split())

if m == 0:
    print(1)
    exit()

for _ in range(m):
    a,b = map(int, sys.stdin.readline().split())

    if not b in graph[a]:
        graph[a].add(b)
    if not a in graph[b]:
        graph[b].add(a)

visited = set()
maxi = 0

def dfs(start):
    stk = [start]
    visited.add(start)
    temp = 1

    while stk:
        cur = stk.pop()

        for c in graph[cur]:
            if not c in visited:
                visited.add(c)
                stk.append(c)
                temp += 1

    return temp

for j in graph:
    if not j in visited:
        cnt = dfs(j)
        maxi = max(cnt, maxi)

print(maxi)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):
    score = 1
    for i in range(K):
        score *= A[i]

    prev_score = score
    for i in range(N-K):
        if A[i]!=A[i+K]:
            if A[i]!=1:
                score //= A[i]
            if A[i+K]!=1:
                score *= A[i+K]
        if score>prev_score:
            print(YES)
        else:
            print(NO)
        prev_score = score
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, A: "List[int]"):
    for i in range(N-K):
        if A[i]<A[i+K]:
            print(YES)
        else:
            print(NO)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)

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

n,k=map(int,input().split())
a=list(map(int,input().split()))
x=[]
for i in range(0,n-k+1):
    b=a[i:i+k]
    if min(b)>=0:
        ans=max(b)
    elif max(b)<=0:
        ans=abs(min(b))
    else:
        ans=min(abs(min(b))*2+max(b),abs(min(b))+max(b)*2)
    x.append(ans)
    b=[]         
print(min(x))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
x=[]
for i in range(0,n-k+1):
    ans=a[i+k-1]-a[i]+min(abs(a[i+k-1]),abs(a[i]))
    x.append(ans)        
print(min(x))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
X=0
for i in range(N-1):
  for ii in range(N-i-1):
    X+=A[i]*A[i+ii+1]
    X=X%(10**9+7)
print(X)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
def calc_mod(n):
    return n %(10**9+7)
AA=list(map(calc_mod, A))
X=0
XX=0
for i in range(N-1):
  XX+=AA[N-i-1]
  X+=AA[N-i-2]*XX
  X=X%(10**9+7)
print(X)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n+1):
    ans += i % (i+1)%n
print(ans)


### FIXED CODE ###

n = int(input())
ans = (n+1) * (n//2) - n
if n%2 == 1:
    ans += n//2 + 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from operator import itemgetter
import heapq


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    A = set(v for v, cost in L[0])
    W = weight[1:]
    index = 0

    while V:
        swap = False
        for v, cost in L[index]:
            if v not in A:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])


        a = min(W, key=itemgetter(0))
        index = a[1]
        W.remove(a)

        A.update(v for v, cost in L[index])
        A.remove(index)
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()
### BUGGY CODE ###

import math

n, m = [int(i) for i in input().split()]
a = [-1]
for mi in range(m):
    a.append(int(input()))
a.append(n+1)

ans = 1
for mi in range(1, m+2):
    if a[mi] == a[mi-1]:
        break
    elif a[mi] == a[mi-1] + 1:
        ans = 0
        break
    k = a[mi] - a[mi-1] - 2
    max_2 = k//2
    cnt = 0
    for i in range(max_2+1):
        cnt += math.factorial(k-i) // (math.factorial(k-2*i) * math.factorial(i)) % 1000000007
    ans = ans * cnt % 1000000007
    if ans == 0:
        break

print(ans)


### FIXED CODE ###

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

b = [0 for i in range(n+1)]

for mi in range(m):
    b[int(input())] = 1
cnt = 0
s = [0 for i in range(n+1)]
s[0] = 1
if b[1] == 0:
    s[1] = 1
else:
    s[1] = 0
for ni in range(2,n+1):
    if b[ni] == 0:
        s[ni] = (s[ni-1] + s[ni-2]) % 1000000007
    else:
        s[ni] = 0
print(s[n])
### BUGGY CODE ###

import fractions
mod = 10**9+7
def LCM(a,b):
    return a*b//fractions.gcd(a,b)

N=int(input())
A = [int(i) for i in input().split()]
curLCM = A[0]
for i in range(1,N):
    curLCM = LCM(curLCM,A[i])
ans = 0
for a in A:
    ans += curLCM//a 
    ans %= mod
print(ans)

### FIXED CODE ###

import fractions
mod = 10**9+7
def LCM(a,b):
    return a*b//fractions.gcd(a,b)

N=int(input())
A = [int(i) for i in input().split()]
curLCM = A[0]
for i in range(1,N):
    curLCM = LCM(curLCM,A[i])
ans = 0
for a in A:
    ans += curLCM//a 
print(ans%mod)
### BUGGY CODE ###

S = input()
N = int(input())
direct = 0
for i in range(N):
  X = input().split()
  if len(X) == 1:
    direct = 1 - direct
  else:
    if (X[1] == "1" and direct == 0) or (X[1] == "2" and direct == 1):
      S = X[2] + S
    else:
      S = S + X[2]
print(S) if direct == 0 else print(S[::-1])


### FIXED CODE ###

S = input()
f = ""
N = int(input())
direct = 0
for i in range(N):
  X = input().split()
  if len(X) == 1:
    direct = 1 - direct
  else:
    if (X[1] == "1" and direct == 0) or (X[1] == "2" and direct == 1):
      f += X[2]
    else:
      S += X[2]
print(f[::-1]+S) if direct == 0 else print(S[::-1]+f)
### BUGGY CODE ###

INF = 1000000
N = int(input())
S = input()

"""
まあまずは愚直にOrder（N*N）でやろう
"""

ans = INF

for i in range(N):
  count = 0
  for t in range(N):
    if i == t:
      continue
    if t < i and S[t] == "W" or t > i and S[t] == "E":
      count += 1

  ans = min(ans, count)

print(ans)

### FIXED CODE ###

"""
まあまずは愚直にOrder（N*N）でやろう
これナイーブ計算というらしい
→無理でした。

前処理でWの累積和を計算する
そのあとにインデックス回して最小値を計算する
確かに前処理がO(N)でできるなら、
O(N)　＋　O（N）で計算可能になる！！
"""

INF = 1000000
N = int(input())
S = input()
ans = INF

sum_n = [0]
add_n = 0
# 前処理
# Westを向いている人の数を数える
for s in S:
  if s == "W":
    add_n += 1
  sum_n.append(add_n)

# リーダーの添字 = i
for i in range(N):
  # i番目より西にいる人のWを向いている人の数
  if i > 0:
    b_i = sum_n[i] - sum_n[0]
  else:
    b_i = 0

  # i番目より東にいる人のWを向いている人の数
  if i < N:
    f_i = (N - (i + 1)) - (sum_n[N] - sum_n[i+1])
  else:
    f_i = 0
  
  tmp = b_i + f_i
  ans = min(ans, tmp)

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

INTMAX = (1<<31) - 1

def ans():
    for i in range(_N):
        x = i+OFS#N-1
        A[x] = arr[i]
        while x > 1:
            x >>= 1
            y = x<<1
            l = A[y]
            r = A[y+1]
            A[x] = l if l < r else r#min(l,r)

    res = [0]*(_N-k+1)
    for i in range(_N-k+1):
        l = i+OFS#N-1
        r = i+k+OFS#N-1
        z = INTMAX
        while l < r:
            if l & 1:
                p = A[l]
                z = p if p < z else z
                l += 1
            if r & 1:
                r -= 1
                p = A[r]
                z = p if p < z else z
            l >>= 1
            r >>= 1
        res[i] = z
    print(*res)

_N,k = map(int,input().split())
*arr, = map(int,input().split())
N = 1
N = 2**(_N-1).bit_length()
OFS = N - 1
A = [INTMAX]*(N<<1)
ans()



### FIXED CODE ###

INTMAX = (1<<31) - 1

def ans():
    for i in range(k):
        x = i + OFS
        A[x] = arr[i]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r#min(tree[left],tree[right])
    res = []
    c = 0
    for i in range(_N-k):
        res.append(A[0])
        x = c + OFS
        A[x] = arr[i+k]
        while True:
            if(x <= 0):
                break
            x = (x - 1)//2
            l = A[x*2+1]
            r = A[x*2+2]
            A[x] = l if l < r else r
        c += 1
        if(c == k):
            c = 0
    res.append(A[0])
    print(*res)

_N,k = map(int, input().split())
*arr, = map(int,input().split())
if(k==1):
    print(*arr)
else:
    N = 2**(_N-1).bit_length()
    A = [INTMAX]*(2*N)
    OFS = N - 1
    ans()
### BUGGY CODE ###

from bisect import bisect_left
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]

u = [-i for i in s[::-1]]
v = [-i for i in t[::-1]]

for _ in range(Q):
    x = int(input())

    # x -> s -> t
    dist1, dist2 = 0, 0
    p1 = bisect_left(s, x)
    p2 = bisect_left(u, -x)
    x1, x2 = s[p1-1], -u[p2-1]
    dist1 += abs(x-x1)
    dist2 += abs(x-x2)

    p3 = bisect_left(t, x1)
    p4 = bisect_left(v, -x1)
    x3, x4 = t[p3-1], -v[p4-1]
    dist1 += min(abs(x1-x3),abs(x1-x4))

    p3 = bisect_left(t, x2)
    p4 = bisect_left(v, -x2)
    x3, x4 = t[p3-1], -v[p4-1]
    dist2 += min(abs(x2-x3),abs(x2-x4))

    dist_st = min(dist1, dist2)

    # x -> t -> s

    dist1, dist2 = 0, 0
    p1 = bisect_left(t, x)
    p2 = bisect_left(v, -x)
    x1, x2 = t[p1-1], -v[p2-1]
    dist1 += abs(x-x1)
    dist2 += abs(x-x2)

    p3 = bisect_left(s, x1)
    p4 = bisect_left(u, -x1)
    x3, x4 = s[p3-1], -u[p4-1]
    dist1 += min(abs(x1-x3),abs(x1-x4))

    p3 = bisect_left(s, x2)
    p4 = bisect_left(u, -x2)
    x3, x4 = s[p3-1], -u[p4-1]
    dist2 += min(abs(x2-x3),abs(x2-x4))

    dist_ts = min(dist1, dist2)

    print(min(dist_st, dist_ts))

### FIXED CODE ###

from bisect import bisect_left
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]+[10**15]
t = [int(input()) for _ in range(B)]+[10**15]

for _ in range(Q):
    x = int(input())

    # x -> s -> t
    dist1, dist2 = 0, 0
    p1 = bisect_left(s, x)
    x1, x2 = s[p1-1], s[p1]
    dist1 += abs(x-x1)
    dist2 += abs(x-x2)

    p3 = bisect_left(t, x1)
    x3, x4 = t[p3-1], t[p3]
    dist1 += min(abs(x1-x3),abs(x1-x4))

    p3 = bisect_left(t, x2)
    x3, x4 = t[p3-1], t[p3]
    dist2 += min(abs(x2-x3),abs(x2-x4))

    dist_st = min(dist1, dist2)

    # x -> t -> s

    dist1, dist2 = 0, 0
    p1 = bisect_left(t, x)
    x1, x2 = t[p1-1], t[p1]
    dist1 += abs(x-x1)
    dist2 += abs(x-x2)

    p3 = bisect_left(s, x1)
    x3, x4 = s[p3-1], s[p3]
    dist1 += min(abs(x1-x3),abs(x1-x4))

    p3 = bisect_left(s, x2)
    x3, x4 = s[p3-1], s[p3]
    dist2 += min(abs(x2-x3),abs(x2-x4))

    dist_ts = min(dist1, dist2)

    print(min(dist_st, dist_ts))
### BUGGY CODE ###

from sys import stdin
import numpy as np
 
n,m = [int(x) for x in stdin.readline().rstrip().split()]
a_lst = np.array([int(x) for x in stdin.readline().rstrip().split()])

for i in range(m):
  a_lst[np.argmax(a_lst)] = a_lst[np.argmax(a_lst)] // 2
  
print(np.sum(a_lst))

### FIXED CODE ###

from sys import stdin
import heapq

n,m = [int(x) for x in stdin.readline().rstrip().split()]
a_lst = [int(x) * (-1) for x in stdin.readline().rstrip().split()]
heapq.heapify(a_lst)

for i in range(m):
  tmp = heapq.heappop(a_lst)
  tmp = (-1) * ((-1*tmp)//2)
  heapq.heappush(a_lst, tmp)
  
print(-sum(a_lst))
### BUGGY CODE ###

def main():
    from math import ceil
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()))
    A.reverse()
    ok = max(a * f for a, f in zip(A, F))
    ng = -1
    while ok - ng != 1:
        x = (ok + ng) // 2
        cnt = 0
        for a, f in zip(A, F):
            if a * f > x:
                cnt += ceil(a - x / f)
            if cnt > k:
                ng = x
                break
        else:
            ok = x

    print(ok)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from math import ceil
    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    F = sorted(map(int, input().split()))
    A.reverse()
    ok = max(a * f for a, f in zip(A, F))
    ng = -1
    while ok - ng != 1:
        x = (ok + ng) // 2
        cnt = 0
        for a, f in zip(A, F):
            if a * f > x:
                cnt += ceil(a - x / f)
            if cnt > k:
                ng = x
                break
        else:
            ok = x

    print(ok)

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

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])


### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])
### BUGGY CODE ###

n = int(input())
height = list(map(int, input().split()))
max_count = 0
for i in range(n):
    count = 0
    for j in range(i, n):
        if j == n - 1 or height[j] < height[j + 1]:
            break
        count += 1
    max_count = max(max_count, count)
print(max_count)


### FIXED CODE ###

n = int(input())
height = list(map(int, input().split()))
max_count = 0
count = 0
for i in range(n - 1):
    if height[i] < height[i + 1]:
        max_count = max(count, max_count)
        count = 0
        continue
    count += 1
max_count = max(count, max_count)
print(max_count)
### BUGGY CODE ###

S = str(input())
N = len(S)
cnt = 0

for i in range(N):
    for j in range(i+1,N):
        if len(S[i:j+1]) >= 4:
            if int(S[i:j+1]) % 2019 == 0:
                cnt += 1
            
print(cnt)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  num = int(input())
  if num in A:
    A.remove(num)
  else:
    A.append(num)
print(len(A))

### FIXED CODE ###

N = int(input())
A = [input() for i in range(N)]
dic={}
for a in A:
  if a not in dic:
    dic[a] = 1
  elif dic[a] != 1:
    dic[a] = 1
  else:
    dic[a] = 0
print(list(dic.values()).count(1))
### BUGGY CODE ###

import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
A_sort = list(np.sort(A)[::-1])
A_index = list(np.argsort(A)[::-1])

dp = [[-float('inf')]*(N+1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
    pi = A_index[i]  #もともといた場所
    for l in range(i+1): 
        r = i - l   #右を選んだ回数
        dp[i+1][l+1] = max(dp[i+1][l+1],dp[i][l] + A_sort[i] * (pi-l)) 
        dp[i+1][l] = max(dp[i+1][l],dp[i][l] + A_sort[i] * ((N-r-1)-pi))

print(max(dp[N]))

### FIXED CODE ###

import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

A = [(A[i], i) for i in range(N)]
A_sort = sorted(A,reverse = True)

dp = [-float('inf')]*(N+1)
dp[0] = 0

for i in range(N):
    dp_new = [-float('inf')]*(N+1)
    pi = A_sort[i][1]  #もともといた場所
    for l in range(i+1): 
        r = i - l   #右を選んだ回数
        dp_new[l+1] = max(dp_new[l+1],dp[l] + A_sort[i][0] * (pi-l)) 
        dp_new[l] = max(dp_new[l],dp[l] + A_sort[i][0] * ((N-r-1)-pi))
    dp = dp_new
print(max(dp))
### BUGGY CODE ###

n = int(input())
points=[]
summaxp=[]
summinp=[]
diffmaxp=[]
diffminp=[]

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y
    if not [x,y] in points:
        points.append([x,y])
        if x+y > summax:
            summaxp=[[x,y]]
            summax = x+y
        elif x+y == summax:
            summaxp.append([x,y])
        if x+y < summin:
            summinp=[[x,y]]
            summin = x+y
        elif x+y == summin:
            summinp.append([x,y])
        if x-y > diffmax:
            diffmaxp=[[x,y]]
            diffmax = x-y
        elif x-y == diffmax:
            diffmaxp.append([x,y])
        if x-y < diffmin:
            diffminp=[[x,y]]
            diffmin = x-y
        elif x-y == diffmin:
            diffminp.append([x,y])

a = summax-summin
b = diffmax-diffmin
sol = max(a,b)
print(sol)

### FIXED CODE ###

n = int(input())

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y

    if x+y > summax:
        summax = x+y
    if x+y < summin:
        summin = x+y
    if x-y > diffmax:
        diffmax = x-y
    if x-y < diffmin:
        diffmin = x-y

a = summax-summin
b = diffmax-diffmin
sol = max(a,b)
print(sol)
### BUGGY CODE ###

s = input()
q = int(input())
ans = s
for i in range(q):
    arr = list(map(str, input().split()))
    if arr[0] == '1':
        ans = ans[::-1]
    else:
        if arr[1] == '1':
            ans = arr[2] + ans
        else:
            ans += arr[2]
print(ans)


### FIXED CODE ###

from collections import deque


s = list(input())
q = int(input())
ans = deque(s)
cnt = 0
for i in range(q):
    arr = list(map(str, input().split()))
    if arr[0] == '1':
        cnt += 1
        cnt %= 2
    else:
        if (arr[1] == '1' and cnt == 0) or (arr[1] == '2' and cnt == 1):
            ans.appendleft(arr[2])
        else:
            ans.append(arr[2])
if cnt == 0:
    print(*ans, sep='')
else:
    ans.reverse()
    print(*ans, sep='')
### BUGGY CODE ###

n=int(input())
p=1
for i in range(1,n+1):
  p*=i
print(p%(10**9+7))

### FIXED CODE ###

n=int(input())
p=1
for i in range(1,n+1):
  p*=i
  p=p%(10**9+7)
print(p)
### BUGGY CODE ###

N = int(input())
ans = ''
while N != 1:
    if abs(N) % 2 == 1:
        ans += '1'
        N = (N-1) // -2
    else:
        ans += '0'
        N = N // -2
ans += '1'
print(ans[::-1])

### FIXED CODE ###

N = int(input())
ans = ''
if N == 0:
    print(0)
    quit()
while N != 1:
    if abs(N) % 2 == 1:
        ans += '1'
        N = (N-1) // -2
    else:
        ans += '0'
        N = N // -2
ans += '1'
print(ans[::-1])
### BUGGY CODE ###

N = int(input())
s_list=[]
for i in range(N):
    s_list.append(sorted(list(input())))
set_list=list(map(list, set(map(tuple, s_list))))

import math

count=0
for element in set_list:
    many = s_list.count(element)
    if many>1:
        count+=math.factorial(many) // (math.factorial(many - 2) * math.factorial(2))

print(count)

### FIXED CODE ###

N = int(input())
s_list=[]
s_dict={}
count=0

for i in range(N):
    s = "".join(sorted(input()))
    if s not in s_dict:
        s_dict[s]=0
    else:
        s_dict[s]+=1
        count+=s_dict[s]
print(count)