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

from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    # dp
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        # add left
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        # add right
        for j in range(n):
            dp[i + 1, j] = max(dp[i, j] + (-a) * abs(n - 1 - (i - j) - k), dp[i + 1, j])
        # dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, -1 - i, -1)), dp[i + 1, :-1])

    # print(dp)
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


if __name__ == "__main__":
    test()
    main()


### FIXED CODE ###

from heapq import heappop, heappush
import numpy as np


def solve(n, a_list):
    h = []
    for i in range(n):
        heappush(h, (-a_list[i], i))
    # dp
    dp = (-10 ** 18) * np.ones((n + 1, n + 1), dtype=np.int)
    dp[0, 0] = 0
    for i in range(n):
        a, k = heappop(h)
        # add left
        dp[i + 1, 1:] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n)), dp[i + 1, 1:])
        # add right
        # for j in range(n):
        #    dp[i + 1, j] = max(dp[i, j] + (-a) * abs(n - 1 - (i - j) - k), dp[i + 1, j])
        dp[i + 1, :-1] = np.maximum(dp[i, :-1] + (-a) * np.abs(k - np.arange(n - 1 - i, n + n - 1 - i)), dp[i + 1, :-1])

    # print(dp)
    res = dp[-1, :].max()
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 3, 4, 2]) == 20
    assert solve(6, [5, 5, 6, 1, 1, 1]) == 58
    assert solve(6, [8, 6, 9, 1, 2, 1]) == 85
    # print(solve(2000, [0] * 2000))


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = [(0, 0)]
g = (h - 1, w - 1)
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = float('inf')
dist = [[inf] * w for _ in range(h)]
dist[0][0] = 0
cnt = 0
while 1:
    qq = []
    cnt += 1
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1:
                continue
            if s[yy][xx] == '#' or dist[yy][xx] != inf:
                continue
            dist[yy][xx] = cnt
            qq.append((yy, xx))
    q = qq
    if g in q:
        break
    if q:
        continue
    else:
        print(-1)
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt += 1
print(h * w - cnt - 1)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = [(0, 0)]
g = (h - 1, w - 1)
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
inf = float('inf')
dist = [[inf] * w for _ in range(h)]
dist[0][0] = 0
cnt = 0
while 1:
    qq = []
    cnt += 1
    for y, x in q:
        for dy, dx in test:
            yy, xx = y + dy, x + dx
            if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1:
                continue
            if s[yy][xx] == '#' or dist[yy][xx] != inf:
                continue
            dist[yy][xx] = cnt
            qq.append((yy, xx))
    q = qq
    if g in q:
        break
    if q:
        continue
    else:
        print(-1)
        exit()
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            cnt += 1
print(h * w - cnt - 1)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

# d = [[2001] * W for _ in range(H)]


def bfs(q):
    res_q = deque()
    while len(q):
        x, y = q.popleft()
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx = x + dx
            ny = y + dy

            if (0 <= nx < H) and (0 <= ny < W) and grid[nx][ny] != '#':
                res_q.append((nx, ny))
                grid[nx][ny] = '#'
    return res_q


q = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            q.append((i, j))

res = 0
while len(q):
    res += 1
    q = bfs(q)

print(res - 1)
### BUGGY CODE ###

import sys

N = int(input())
s = []
for _ in range(N):
    s.append(sorted(input()))

count = 0
for x in range(N):
    for y in range(x + 1, N):
        if s[x] == s[y]:
            count += 1
print(count)

### FIXED CODE ###

import sys
input=sys.stdin.readline

N = int(input())
hash = {}
count = 0
for _ in range(N):
    x = "".join(sorted(input()))
    if x in hash:
        count += hash[x]
    else:
        hash[x] = 0
    hash[x] += 1

print(count)
### BUGGY CODE ###

from collections import Counter

N, M = map(int, input().split())
cnt = Counter()

for i in range(M):
    l, r = map(int, input().split())
    for i in range(l, r + 1):
        cnt[i] += 1

ans = 0
for v in cnt.values():
    if v == M:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter

N, M = map(int, input().split())
L = []
R = []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

maxL = max(L)
minR = min(R)

ans = max(0, minR - maxL + 1)
print(ans)
### BUGGY CODE ###

input()
a = list(map(int, input().split()))
ans = 1
flag = False
for i in a:
    ans *= i
if ans<1000000000000000001:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

import sys
input()
a = list(map(int, input().split()))
ans = 1
flag = False
for i in a:
    if i==0:
        print(0)
        sys.exit()
for i in a:
    ans *= i
    if ans>1000000000000000001:
        print(-1)
        sys.exit()
if ans<1000000000000000001:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    hyouka = [0]*(N-K+1)
    
    for i in range(N-K+1):
        kekka = 1
        for j in As[i:i+K]:
            kekka *= j
            hyouka[i]=kekka
    #print(hyouka)
    for j in range(len(hyouka)):
        if j>0:
            if hyouka[j] > hyouka[j-1]:
                print('Yes')
            else:
                print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))
    hyouka = [0]*(N-K+1)
    """
    kekka = 1
    for i in range(N-K+1):
        if i == 0:
            for j in As[i:i+K]:
                kekka *= j
                hyouka[i]=kekka
        else:
            kekka = kekka/As[i-1]*As[i+K-1]
            hyouka[i]=int(kekka)
    #print(hyouka)
    for j in range(len(hyouka)):
        if j>0:
            if hyouka[j] > hyouka[j-1]:
                print('Yes')
            else:
                print("No")
    """
    for i in range(N-K):
        if As[i] < As[i+K]:
            print("Yes")
        else:
            print("No")


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

s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
for i in reversed(range(0, N)):
    x = s[i:N]
    y = int(x)
    array[y%2019] += 1

for i in array:
    count += i*(i-1)/2
print(int(count))


### FIXED CODE ###

s = str(input())
N = len(s)
array = [0]*2019
array[0] += 1
count = 0
d = 1
r = 0
for i in reversed(range(0, N)):
    r = ( r + int( s[i] ) * d ) % 2019
    d = d * 10 % 2019
    array[r] += 1
for i in array:
    count += i*(i-1)/2
print(int(count))
### BUGGY CODE ###

s = input()
q = int(input())

for _ in range(q):
    t = input()
    if t == '1':
        s = s[::-1]
    else:
        t, f, c = t.split()
        if f == '1':
            s = c + s
        else:
            s = s + c

print(s)

### FIXED CODE ###

#TLE
from collections import deque
s = deque(input())
q = int(input())
num = 0
for _ in range(q):
    t = input()
    if t == '1':
        if num == 0:
            num = 1
        else:
            num = 0
    else:
        t, f, c = t.split()
        if num == 0:
            if f == '1':
                s.appendleft(c)
            else:
                s.append(c)
        else:
            if f == '2':
                s.appendleft(c)
            else:
                s.append(c)
s = ''.join(s)
if num == 1:
    s = s[::-1]
print(s)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
k=[[0]*20 for i in range(n)]
for i in range(n):
    for j in range(20):
        k[i][j] = 1 if (a[i] % 2**(j+1)) >= 2**j else 0
l=0
r=0
c20=[0]*20
r0=-1
ans=[0]*n
while l < n:
    if r > r0:
        for _ in range(20):
            c20[_]+=k[r][_]
    else:
        for _ in range(20):
            c20[_]-=k[l-1][_]
    l0=l
    r0=r
    if sum(list(map(lambda x:x>1 ,c20))) == 0:
        ans[l]=max(ans[l],r)
        if r < n-1:
            r+=1
        else:
            l+=1
    else:
        ans[l]=max(ans[l],r-1)
        l+=1
s=0
for i in range(n):
    s+=ans[i]-i+1
print(s)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
l=0
r=0
now=0
ans=[0]*n
while l < n:
    if r < n and now^a[r] == now + a[r]:
        now += a[r]
        ans[l]=r
        r+=1
    else:
        now -= a[l]
        l+=1
        ans[l-1]=r-1
print(sum([ans[i]-i+1 for i in range(n)]))
### BUGGY CODE ###

S = input()
T = input()
a_idx = ord('a')
S_Lis = {}
T_Lis = {}
leng = len(S)
for i in range(leng):
    s_idx = ord(S[i])-a_idx
    t_idx = ord(T[i])-a_idx
    if s_idx in S_Lis:
        S_Lis[s_idx].append(i)
    else:
        S_Lis[s_idx] = [i]
    if t_idx in T_Lis:
        T_Lis[t_idx].append(i)
    else:
        T_Lis[t_idx] = [i]
    if S_Lis[s_idx] != T_Lis[t_idx]:
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

S = input()
T = input()
a_idx = ord('a')
S_Lis = {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 9: [], 10: [], 11: [], 12: [],
         13: [], 14: [], 15: [], 16: [], 17: [], 18: [], 19: [], 20: [], 21: [], 22: [], 23: [], 24: [], 25: []}
T_Lis = {0: [], 1: [], 2: [], 3: [], 4: [], 5: [], 6: [], 7: [], 8: [], 9: [], 10: [], 11: [], 12: [],
         13: [], 14: [], 15: [], 16: [], 17: [], 18: [], 19: [], 20: [], 21: [], 22: [], 23: [], 24: [], 25: []}
leng = len(S)
for i in range(leng):
    S_Lis[ord(S[i])-a_idx].append(i)
    T_Lis[ord(T[i])-a_idx].append(i)
for i in range(26):
    tmpS = S_Lis[i]
    if len(tmpS) == 0 or tmpS == T_Lis[i]:
        continue
    else:
        flag = True
        for j in T_Lis.values():
            if tmpS == j:
                flag = False
                break
        if flag:
            print("No")
            exit()
print("Yes")
### BUGGY CODE ###

n,k = [int(x) for x in input().split()]
s = {}

for i in input().split():
    if(i in s):
        s[i] += 1
    else:
        s[i] = 1

t = sorted(s.items(), key=lambda x: x[1])

a = 0

while len(t) > k:
    a += t.pop(0)[1]

print(a)


### FIXED CODE ###

n,k = [int(x) for x in input().split()]
s = {}

for i in input().split():
    if(i in s):
        s[i] += 1
    else:
        s[i] = 1


t = list(s.values())
t.sort()
a = sum(t[0:-k])

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

import numpy as np

n=int(input())
E=[]
W=[]
node_l=np.zeros(n)
node_l[0]=1
for i in range(n-1):
    u,v,w=map(int,input().split())
    #print(u,v,w)
    E.append([u,v])
    W.append(w)
#print(E,W)

def bfs(node,node_l,l,w_l,count):
    i=0
    for edge in l:
        if edge[0]==node:
            if node_l[edge[1]-1]==0:
                if W[i]%2==0:
                    node_l[edge[1]-1]=node_l[node-1]
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[1],node_l,l,w_l,count)
                else:
                    node_l[edge[1]-1]=node_l[node-1]*-1
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[1],node_l,l,w_l,count)
        elif edge[1]==node:
            if node_l[edge[0]-1]==0:
                if W[i]%2==0:
                    node_l[edge[0]-1]=node_l[node-1]
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[0],node_l,l,w_l,count)
                else:
                    node_l[edge[0]-1]=node_l[node-1]*-1
                    count+=1
                    if count>=n:
                        return
                    bfs(edge[0],node_l,l,w_l,count)
        i+=1
    return

count=1
bfs(1,node_l,E,W,count)
for i in range(n):
    if node_l[i]==1:
        print('1',end='\n')
    else:
        print('0',end='\n')

### FIXED CODE ###

import numpy as np

n=int(input())
E=[]
node_l=np.zeros(n)
node_l[0]=1
for i in range(n-1):
    u,v,w=map(int,input().split())
    #print(u,v,w)
    E.append((u,v,w))
#print(E,W)

def bfs(node,l):
    root=[[] for i in range(n)]
    for a,b,c in l:
        root[a-1]+=[(b-1,c)]
        root[b-1]+=[(a-1,c)]
    stack=[]
    stack.append(node-1)
    #print(root)
    dist=[-1]*n
    dist[node-1]=0
    while stack:
        #print(stack)
        buf=stack.pop(-1)
        for v,weight in root[buf]:
            if dist[v]==-1:
                dist[v]=dist[buf]+weight
                stack.append(v)
    return dist

for i in bfs(1,E):
    print(i%2,end='\n')
### BUGGY CODE ###

from collections import defaultdict
import bisect
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

fact_memo = [0]*201
fact_memo[0] = 1
def fact(n):
    if fact_memo[n] == 0:
        fact_memo[n] = n*fact(n-1)%mod
    return fact_memo[n]

fact_inv_memo = [0]*201
fact_inv_memo[0] = 1
def fact_inv(n):
    if fact_inv_memo[n] == 0:
        fact_inv_memo[n] = pow(fact(n),mod-2,mod)
    return fact_inv_memo[n]

dp = defaultdict(lambda :-1)
import sys
sys.setrecursionlimit(100000000)
def rec(n,x):
    if dp[(n,x)] != -1:
        return dp[(n,x)]
    if n == 0:
        dp[(n,x)] = x%S[0]
        return dp[(n,x)]
    s = S[:n+1]
    if x <= s[-1]:
        k = bisect.bisect(s,x)
        if k == 0:
            dp[(n,x)] = x*fact(n+1)%mod
        else:
            dp[(n,x)] = fact(n+1)*fact_inv(k)*rec(k-1,x)%mod
    else:
        res = rec(n-1,x%s[-1])+n*rec(n-1,x)
        dp[(n,x)] = res%mod
    return dp[(n,x)]

print(rec(N-1,X))

### FIXED CODE ###

from collections import defaultdict
N,X = map(int,input().split())
S = list(map(int,input().split()))
S.sort()
mod = 10**9+7

fact_memo = [0]*201
fact_memo[0] = 1
def fact(n):
    if fact_memo[n] == 0:
        fact_memo[n] = n*fact(n-1)%mod
    return fact_memo[n]

fact_inv_memo = [0]*201
fact_inv_memo[0] = 1
def fact_inv(n):
    if fact_inv_memo[n] == 0:
        fact_inv_memo[n] = pow(fact(n),mod-2,mod)
    return fact_inv_memo[n]

dp = defaultdict(lambda :[-1]*(X+1))
for n in range(N):
    for x in range(X+1):
        if n == 0:
            dp[n][x]=x%S[0]
        else:
            dp[n][x]=(dp[n-1][x%S[n]]+n*dp[n-1][x])%mod

print(dp[N-1][X])
### BUGGY CODE ###

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

for i in range(n):
  if a[n-1-i] ^ c[n-1-i]%2:
    b.add(n-i)
    for j in range(1, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        c[j-1] += 1
        if (n-i)//j != j:
          c[(n-i)//j -1] += 1

print(len(b))
if len(b)>0:
  print(*b)

### FIXED CODE ###

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

for i in range(n-1):
  if a[n-1-i]&1:
    b.add(n-i)
    for j in range(2, int((n-i)**0.5)+1):
      if (n-i)%j == 0:
        a[j-1] += 1
        if (n-i)//j != j:
          a[(n-i)//j -1] += 1
if a[0] != len(b)%2:
  b.add(1)
          
print(len(b))
if len(b)>0:
  print(*b)
### BUGGY CODE ###

import math
def combinations(n, r):
  if n == r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
s = [[sorted(list(input())),1]]
ans = 0
for i in range(N-1):
  s_i = sorted(list(input()))
  flag = 0
  for j in range(len(s)):
    if s[j][0] == s_i:
      flag = 1
      s[j][1] += 1
      break
  if flag != 1:
    s.append([s_i,1])
for j in range(len(s)):
    tmp = s[j][1]
    if tmp != 1:
      ans += combinations(tmp,2)
print(ans)

### FIXED CODE ###

import math
def combinations(n, r):
  if n == r:
    return 1
  else:
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())
s = [sorted(input())]
ans = 0
for i in range(N-1):
  s_i = sorted(input())
  s.append(s_i)
s = sorted(s)
count=1
for j in range(N-1):
  if s[j] == s[j+1]:
    count+=1
  else:
    if count != 1:
      ans += combinations(count,2)
    count=1
if count != 1:
  ans += combinations(count,2)
print(ans)
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
tmp = [A[0]]
ans = 0
for i in range(1, N):
    index = bisect.bisect_left(tmp, A[i])
    if index == 0:
        tmp.append(A[i])
        tmp.sort()
    else:
        tmp[index-1] = A[i]

print(len(tmp))


### FIXED CODE ###

import bisect
N = int(input())
A = [-int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect(tmp, i)
    if index == len(tmp):
        tmp.append(i)
    else:
        tmp[index] = i

print(len(tmp))
### BUGGY CODE ###

input()
a=[]
for i in input().split():
	a.append(int(i))

maxp = 0
b=[]
for i in range(len(a)):
	for j in range(len(a))[i+1:]:
		d=a[j]-a[i]
		if d>maxp:
			maxp=d
		b.append(d)
c=0
for i in b:
	if i==maxp:
		c+=1

print(c)

### FIXED CODE ###

input()
a=[]
for i in input().split():
	a.append(int(i))

maxp = 0
minp = 10000000000000
maxval=0
c=0
for i in range(len(a)):
	if a[i]<minp:
		minp=a[i]
	val=a[i]-minp
	if val>maxval:
		maxval=val
		c=1
	elif val==maxval:
		c+=1

print(c)
### BUGGY CODE ###

#coding: utf-8
N, M = map(int, input().split())
points = list(map(int, input().split()))
points.sort()
koma = [points[i+1] - points[i] for i in range(M-1)]
sum_ = 0
for i in range(M-N):
  sum_ += min(koma)
  koma.remove(min(koma))
print(sum_)

### FIXED CODE ###

#coding: utf-8
N, M = map(int, input().split())
points = list(map(int, input().split()))
if N > M:
  print(0)
else:
  points.sort()
  koma = [points[i+1] - points[i] for i in range(M-1)]
  koma.sort()
  print(sum(koma[:M-N]))
### BUGGY CODE ###

n = int(input())
table = [[0 for i in range(3)] for k in range(n-1)]
for i in range(n-1):
	c,s,f = map(int,input().split())
	table[i][0] = c
	table[i][1] = s
	table[i][2] = f
for i in range(n-1):
	total = table[i][1]+table[i][0]
	for k in range(i+1,n-1):
		if total <= table[k][1]:
			total = table[k][1] + table[k][0]
		else:
			times = 1
			while (times*table[k][2] + table[k][1]) < total:
				times += 1
			total = times*table[k][2] + table[k][1] + table[k][0]
	print(total)
print('0')

### FIXED CODE ###

n = int(input())
table = [[0 for i in range(3)] for k in range(n-1)]
for i in range(n-1):
	c,s,f = map(int,input().split())
	table[i][0] = c
	table[i][1] = s
	table[i][2] = f
for i in range(n-1):
	total = table[i][1]+table[i][0]
	for k in range(i+1,n-1):
		if total <= table[k][1]:
			total = table[k][1] + table[k][0]
		else:
			sur = total%table[k][2]
			if sur == 0:
				total = total + table[k][0]
			else:
				total = (total - sur) + table[k][2] + table[k][0]
	print(total)
print('0')
### BUGGY CODE ###

import itertools
import sys
N = int(input())
l = [pow(9,(i+1)) for i in range(5)]

for i in range(7):
  l.append(pow(6,i))
ans = 0

for i in range(20):
  for j in itertools.combinations_with_replacement(l,i):
    if sum(j) == N:
      print(len(j))
      sys.exit()

### FIXED CODE ###

import itertools
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N = I()

ans = 10e10
for i in range(N+1):
    j = N-i
    cnt = 0
    while i > 0:
        cnt += i%6
        i //= 6
    while j > 0:
        cnt += j%9
        j //= 9
    ans = min(ans,cnt)

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

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    if num&1 == 0:
        d.add(2)
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i==0:
            d.add(i)
        while num%i==0:
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)