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

N = int(input())
Cs = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

degs = [0] * N
clusters = [[] for _ in range(N)]


def go(curr, fro):
    col = Cs[curr] - 1
    deg = 1
    clust = {}
    for n in adj[curr]:
        if n == fro:
            continue
        ch_deg, ch_clust = yield n, curr
        clusters[col].append(ch_deg - ch_clust.get(col, 0))
        if len(ch_clust) > len(clust):
            clust, ch_clust = ch_clust, clust
        for k, v in ch_clust.items():
            clust[k] = clust.get(k, 0) + v
        deg += ch_deg
    clust[col] = deg
    return deg, clust


stack = [[None, None], [go(0, -1), None]]
while len(stack) > 1:
    gen, val = stack[-1]
    try:
        params = gen.send(val)
    except StopIteration as e:
        stack[-2][1] = e.value
        stack.pop()
    else:
        stack.append([go(*params), None])

_, root_clust = stack[0][1]
for i in range(N):
    clusters[i].append(N - root_clust.get(i, 0))


for clust in clusters:
    tot = (N * N + N) // 2
    for cnt in clust:
        tot -= (cnt * cnt + cnt) // 2
    print(tot)


### FIXED CODE ###

N = int(input())
Cs = list(map(int, input().split()))
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

degs = [0] * N
clusters = [[] for _ in range(N)]


def go(curr, fro):
    col = Cs[curr] - 1
    deg = 1
    clust = {}
    for n in adj[curr]:
        if n == fro:
            continue
        ch_deg, ch_clust = yield n, curr
        clusters[col].append(ch_deg - ch_clust.get(col, 0))
        if len(ch_clust) > len(clust):
            clust, ch_clust = ch_clust, clust
        for k, v in ch_clust.items():
            clust[k] = clust.get(k, 0) + v
        deg += ch_deg
    clust[col] = deg
    return deg, clust


def tramp(gen_fn, *args):
    stack = [gen_fn(*args)]
    val = None
    while stack:
        gen = stack[-1]
        try:
            params = gen.send(val)
        except StopIteration as e:
            stack.pop()
            val = e.value
        else:
            stack.append(go(*params))
            val = None
    return val


_, root_clust = tramp(go, 0, -1)
for i in range(N):
    clusters[i].append(N - root_clust.get(i, 0))


for clust in clusters:
    tot = (N * N + N) // 2
    for cnt in clust:
        tot -= (cnt * cnt + cnt) // 2
    print(tot)
### BUGGY CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

s = []
for i in range(K):
    s.append(p[i])

m = sum(s)
for i in range(K,N):
    s.pop(0)
    s.append(p[i])
    if sum(s) > m:
        m = sum(s)

m += K

print(m / 2)


### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

s = []
for i in range(K):
    s.append(p[i])

m = sum(s)
t = m
for i in range(K, N):
    t += p[i] - p[i - K]
    if m < t:
        m = t

m += K

print(m / 2)
### BUGGY CODE ###

import collections

num = int(input())
word_list = []
for i in range(num):
    word_list.append(input())
word_dict = collections.Counter(word_list)
word_list = [k for k,v in word_dict.items() if v == word_dict.most_common()[0][1]]
word_list.sort()
for word in word_list:
    print(word)

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
num = int(input())
word_list = []
for i in range(num):
    word_list.append(input())
word_dict = collections.Counter(word_list)
most_common = word_dict.most_common()[0][1]
word_list = [k for k,v in word_dict.items() if v == most_common]
word_list.sort()
for word in word_list:
    print(word)
### BUGGY CODE ###


#約数リスト
import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P




def resolve():
    n = int(input())
    A = get_primes(2*n)

    for i in A:
        if i>=n:
            print(i)
            return





if __name__ == "__main__":
    resolve()

### FIXED CODE ###




#約数リスト
import math
#素数列挙
def get_primes(limit):
    A = [i for i in range(2, limit+1)]
    P = []
    time = 0
    
    while True:
        prime = min(A)
        
        if prime > math.sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P




def resolve():
    n = int(input())
    A = get_primes(int(1.2*n))

    for i in A:
        if i>=n:
            print(i)
            return





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

from collections import defaultdict


def dfs(s):
    if s.count("B") == len(s) or s.count("W") == len(s):
        return 0

    ans = 10 ** 20
    stone = s[0]
    t = s[:]
    while t[0] == stone:
        t = t[1:]
    ans = min(ans, dfs(t) + 1)

    stone = s[-1]
    t = s[:]
    while t[-1] == stone:
        t = t[:-1]
    ans = min(ans, dfs(t) + 1)

    return ans


def main():
    s = input()
    print(dfs(list(s)))


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    S = input()

    t = S[0]
    for i in range(1, len(S)):
        if t[-1] != S[i]:
            t += S[i]
    print(len(t) - 1)

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

import sys
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())
a=list(mii())
b=list(mii())
k = []
j = 0
na= 0
c = 0
for i in range(n):
    if a[i]<b[i]:
        na +=b[i]-a[i]
        c+=1
    elif a[i] > b[i]:
        k.append(a[i]-b[i])
    k.sort()
while na > 0 and k:
    na -=k[-1]
    k.pop(-1)
    c +=1
if na > 0:print(-1)
else:print(c)

### FIXED CODE ###

import sys
input=sys.stdin.readline
mii=lambda:map(int,input().split())

n=int(input())
a=list(mii())
b=list(mii())
k = []
j = 0
na= 0
c = 0
for i in range(n):
    if a[i]<b[i]:
        na +=b[i]-a[i]
        c+=1
    elif a[i] > b[i]:
        k.append(a[i]-b[i])
k.sort()
while na > 0 and k:
    na -=k[-1]
    k.pop(-1)
    c +=1
if na > 0:print(-1)
else:print(c)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    m = 0
    for i in range(1, n):
        cnt_m = 0
        cnt = 0
        for j in range(i, n):
            if s[j-i] == s[j]:
                cnt = min(cnt+1, i)
            else:
                cnt_m = max(cnt, cnt_m)
                cnt = 0
        m = max(cnt, cnt_m, m)
    print(m)


main()


### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        cnt_m=0
        cnt=0
        for j in range(i,n):
            if s[j-i]==s[j]:
                cnt=min(cnt+1,i)
            else:
                cnt_m=max(cnt,cnt_m)
                cnt=0
        m=max(cnt,cnt_m,m)
    print(m)

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

n = int(input())
a = [int(x) for x in input().split(' ')]
# a = [int(input()) for x in range (n)]

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[-0]


for x in range(0,mi*2+1,2) :
    # print(x)
    b[0] = x

    for i in range(1,n) :
        b[i] = 2 * a[i-1] - b[i-1]
        # print(b)
        if (b[i] < 0) : 
            break

    else :
        if (b[-1] + b[0] == 2 * a[-1]) :
            break


s = ""
for i in b :
    s = s + str(i) + " " 


print(s)

### FIXED CODE ###

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

b = [0] * n
if(a[0] > a[-1]) : mi = a[-1]
else : mi = a[0]

aa = 0
for i in range(1, n, 2) :
    aa += a[i]
b[0] = sum(a) - 2 * aa

for i in range(1,n) :
    b[i] = 2 * a[i-1] - b[i-1]
print(str(b).strip("[]").replace(",",""))
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 1
for i in range(1,N):
    if P[i] <= min(P[0:i]):
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 1
m = P[0]
for i in range(1,N):
    if P[i] < m:
        cnt += 1
        m = P[i]
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[6]:


N,K,Q = map(int, input().split())
point = [K]*N
for _ in range(Q):
    A = int(input())
    point[A-1] += 1
    point = [p-1 for p in point]
for i in point:
    if i > 0:
        print("Yes")
    else:
        print("No")


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[14]:


N,K,Q = map(int, input().split())
point = [0]*N
for _ in range(Q):
    A = int(input())
    point[A-1] += 1 
ans = [print("Yes") if point[i] > Q-K else print("No") for i in range(len(point))]


# In[ ]:
### BUGGY CODE ###

n, m = map(int, input().split())
AB = [[int(i) for i in input().split()] for i in range(m)]
S = []
G = []

for ab in AB:
    if ab[0] == 1:
        S.append(ab)
    if ab[1] == n:
        G.append(ab)
        
ans = 'IMPOSSIBLE'
for s in S:
    for g in G:
        if s[1] == g[0]:
            ans = 'POSSIBLE'
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
S = set()
G = set()

for i in range(m):
    s, g = map(int, input().split())
    if s == 1:
        G.add(g)
    if g == n:
        S.add(s)

if len(S&G) != 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

# F - Strivore

K = int(input())
S = list(str(input()))
N = len(S)
MOD = 10**9+7

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]
pow25 = [1, 25]
pow26 = [1, 26]

for i in range(2, N+K+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)
    if i <= K+1:
        pow25.append(pow(25, i, MOD))
        pow26.append(pow(26, i, MOD))

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m


ans = 0
for i in range(K+1):
    tmp = pow25[i]
    tmp = (tmp * comb_mod(i+N-1, N-1, MOD)) % MOD
    tmp = (tmp * pow26[K-i]) % MOD
    ans += tmp
    ans %= MOD
print(ans)



### FIXED CODE ###

# F - Strivore

K = int(input())
S = list(str(input()))
N = len(S)
MOD = 10**9+7

fac = [1, 1]
inv = [0, 1]
finv = [1, 1]

for i in range(2, N+K+1):
    fac.append(fac[-1] * i % MOD)
    inv.append(MOD - inv[MOD%i] * (MOD//i) % MOD)
    finv.append(finv[-1] * inv[-1] % MOD)

def comb_mod(n, r, m):
    if (n<0 or r<0 or n<r): return 0
    r = min(r, n-r)
    return fac[n] * finv[n-r] * finv[r] % m

ans = 0
for i in range(K+1):
    tmp = pow(25, i, MOD)
    tmp *= comb_mod(i+N-1, N-1, MOD)
    tmp *= pow(26, K-i, MOD)
    ans += tmp
    ans %= MOD
print(ans)
### BUGGY CODE ###

count, init = tuple(map(int, input().split(" ")))
Xs = [init] + list(map(int, input().split(" ")))
l = [abs(Xs[i]-Xs[i+1]) for i in range(count)]
for i in range(2, min(l)+1)[::-1]:
    if max(map(lambda x: x%i, l)) == 0:
        print(i)
        exit(0)
print(1)

### FIXED CODE ###

from functools import reduce
import numpy as np

def gcd(a, b):
    if b > 0:
        return gcd(b, a%b)
    else:
        return a

def gcd_list(arg_list):
    return reduce(gcd, arg_list)

N, X = tuple(map(int, input().split(" ")))
Xs = [X] + list(map(int, input().split(" ")))
Xs = map(abs, np.diff(Xs))
r = gcd_list(Xs)
print(r)
### BUGGY CODE ###

n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))


### FIXED CODE ###

n = int(input())
s = input()
table = {x: 2**i for i, x in enumerate(map(chr, range(97, 123)))}

SEG_LEN = n
SEG = [0]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = table[x]
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans = SEG[left] | ans
            left += 1
        left //= 2
        if right % 2 == 1:
            ans = SEG[right-1] | ans
            right -= 1
        right //= 2
    return format(ans, 'b').count('1')


for i, c in enumerate(s):
    update(i, c)

q = int(input())
for _ in range(q):
    com, *query = input().split()
    if com == '1':
        idx, x = query
        update(int(idx)-1, x)
    else:
        L, R = map(int, query)
        print(find(L-1, R))
### BUGGY CODE ###


from collections import Counter

def resolve():
  N = int(input())
  countA = Counter([int(x) for x in input().split(" ")])
  Q = int(input())

  sum_A = 0
  for a in countA.keys():
    sum_A += a*countA[a]

  for _ in range(Q):
    B, C = map(int, input().split(" "))
    if B in countA.keys():
      countA[C] += countA.pop(B)
      sum_A = 0
      for a in countA.keys():
        sum_A += a*countA[a]
      print(sum_A)
    else:
      print(sum_A)


if __name__ == "__main__":
  resolve()

### FIXED CODE ###

from collections import Counter

def resolve():
  N = int(input())
  countA = Counter([int(x) for x in input().split(" ")])
  Q = int(input())

  sum_A = 0
  for a in countA.keys():
    sum_A += a*countA[a]

  for _ in range(Q):
    B, C = map(int, input().split(" "))
    if B in countA.keys():
      target_value = countA.pop(B)
      sum_A += (C - B) * target_value
      countA[C] += target_value
      print(sum_A)
    else:
      print(sum_A)


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

lr = [int(i) for i in input().split()]
res = []
for i in range(lr[0], lr[1]+1):
    for j in range(i+1, lr[1]+1):
        res.append((i*j) % 2019)
print(min(res))


### FIXED CODE ###

lr = [int(i) for i in input().split()]
res = []
for i in range(lr[0], lr[1]+1):
    for j in range(i+1, lr[1]+1):
        tmp = (i*j) % 2019
        if tmp == 0:
            print(0)
            exit()
        res.append(tmp)
print(min(res))
### BUGGY CODE ###

n = int(input())
a = [int(e) for e in input().split()]
ans = 1
for i in range(n):
    ans *= a[i]
if ans > 10**18:
    print(-1)   
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = [int(e) for e in input().split()]
ans = 1
if 0 in a:
    print(0)
else:
    for i in range(n):
        ans *= a[i]
        if ans > 10**18:
            print(-1)
            break  
    else:
        print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
A=[]
for t in range(Q):
    l,r=map(int,input().split())
    T=S[l-1:r]
    cnt=0
    for k in range(len(T)-1):
        if T[k:k+2]=='AC':
            cnt+=1
        else:
            continue
    A.append(cnt)
for s in A:
    print(s)

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
    t[i+1]=t[i]+(1 if S[i:i+2]=='AC' else 0)
for i in range(Q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

N = int(input())

clip = []
for i in range(N):
    S = input()
    if S not in clip:
        
        clip.append(S)
        
    
print(len(clip))

### FIXED CODE ###

N = int(input())

clip = set()
for i in range(N):
    S = input()
    clip.add(S)

    
print(len(clip))
### BUGGY CODE ###

N = int(input())


def Lucas(n):
    if n == 0:
        return 2
    elif n == 1:
        return 1
    return Lucas(n - 2) + Lucas(n - 1)


print(Lucas(N))

### FIXED CODE ###

N = int(input())
L = [2, 1]
for i in range(2, N + 1):
    L.append(L[-2] + L[-1])
print(L[-1])
### BUGGY CODE ###

n = int(input())
a = [int(num) for num in input().split()]

count_max = 0
for x in range(min(a), max(a)+1):
    count=0
    for k in a:
        if x-1 <= k <= x+1:
            count += 1 
    count_max = max(count_max, count)

print(count_max)

### FIXED CODE ###

import collections

n = int(input())
a = [int(num) for num in input().split()]

list_num = collections.Counter(a)

count_max = 0
for x in range(min(a), max(a)+1):
    count = list_num[x-1] + list_num[x] + list_num[x+1]
    count_max = max(count_max, count)

print(count_max)
### BUGGY CODE ###

from collections import defaultdict, deque
N,M = map(int,input().split())
abc = []
for i in range(N):
    a,b = map(int,input().split())
    c = b/a
    abc.append((a,b,c))

abc.sort(key=lambda x:x[2],reverse=True)

d = defaultdict(deque)
for a,b,c in abc:
    d[a].append(b)
# print(abc)
# print(d)
now = 1
ans = 0
days = [True] * M
for i in range(M-1,-1,-1):
    tmpk = -1
    tmpv = -1
    dif = M - i
    for k in sorted(d.keys()):
        if k > dif: break
        if d[k][0] > tmpv:
            tmpv = d[k][0]
            tmpk = k
    if tmpk != -1:
        ans += tmpv
        d[tmpk].popleft()
        if not d[tmpk]:
            d.pop(tmpk)
print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
from collections import defaultdict
N,M = map(int,input().split())
jobs = defaultdict(list)
for i in range(N):
    a,b = map(int,input().split())
    if a <= M: jobs[a-1].append(b)
h = []
ans = 0
for i in range(M):
    if jobs[i]:
        for j in jobs[i]:
            heappush(h, -j)
    if len(h) > 0:
        ans += -heappop(h)
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math


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

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%(10**9+7)

A = copy.deepcopy(a)
A.sort()
for i in range(len(A)-1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    ans = combinations_count(n+1,k)-combinations_count((l+n-r),(k-1))
    print(ans)

    

### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

mod = 10**9+7



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


# 階乗 & 逆元計算
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

A = copy.deepcopy(a)
A.sort()
for i in range(n+1):
    if A[i] == A[i+1]:
        double = A[i]
        break

cnt = 0
for i in range(n+1):
    if a[i] == double:
        if cnt == 0:
            l = i+1
            cnt += 1
        else:
            r = i+1
# print(l,r)
for k in range(1,n+2):
    # print(n+1,k,l+n-r,k-1)
    ans = (combinations_count(n+1,k)-combinations_count((l+n-r),(k-1)))%mod
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C


# See:
# https://qiita.com/suecharo/items/30f5d817da4c948c3be6
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right


if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    order = list(x)

    for i in range(n):
        tmp = order[i]
        x.remove(tmp)
        x = quick_sort(x)
        print(x[(n // 2) - 1])
        x = x + [tmp]


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    x = list(map(int, input().split()))
    sorted_x = sorted(x)

    low = sorted_x[(n // 2) - 1]
    high = sorted_x[(n // 2)]

    for i in range(n):
        if x[i] < high:
            print(high)
        else:
            print(low)
### BUGGY CODE ###

A,B,N=map(int,input().split())
x=0
while A*int(x/B)<1 and x<=N:
    x+=1
print(int((A*(x-1))/B))

### FIXED CODE ###

A,B,N=map(int,input().split())
x=B-1
print(int(A*x/B) if x<=N else int(A*N/B))
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=sorted(nl())[::-1]

# val next
l=[(-1,-1)]*(n+1)
l[0]=(a[0],0)
nx_idx=1

ans = 0

for i in range(1,n):
  aa = a[i]
  now = 0
  mx_idx=0
  mx=-1

  cnt=0
  while True:
    cnt+=1

    val = l[now][0]
    nxt = l[now][1]

    nxtv=0
    nxtv=l[nxt][0]
    
    n_val = min(val,nxtv)

    if mx < n_val:
      mx = n_val
      mx_idx = now

    if nxt == a[i]:
      break
    
    if cnt==nx_idx:
      break

    now = nxt

  ans+=mx

  val = l[mx_idx][0]
  nxt = l[mx_idx][1]

 
  l[nx_idx]=(a[i],l[mx_idx][1])
  l[mx_idx]=(mx,nx_idx)

  nx_idx+=1
print(ans)


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=sorted(nl())[::-1]
 
ans=0

cur=0
now=1
for i in range(n-1):
  ans+=a[cur]
  if now==1:
    now=0
    cur+=1
  elif now==0:
    now=1


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

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,m,q = map(int,input().split())
d = [{} for _ in range(n)]
for i in range(m):
    l,r = map(int,input().split())
    l -= 1
    r -= 1
    if r not in d[l].keys():
        d[l][r] = 0
    d[l][r] += 1
for i in range(n-1)[::-1]:
    for k,v in d[i+1].items():
        if k not in d[i]:d[i][k] = 0
        d[i][k] += v
ans = [0]*q
for i in range(q):
    P,Q = map(int,input().split())
    P -= 1
    Q -= 1
    for k,v in d[P].items():
        if k <= Q:
            ans[i] += v
print('\n'.join(str(i) for i in ans))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n,m,q = map(int,input().split())
d = [{} for _ in range(n)]
for i in range(m):
    l,r = map(int,input().split())
    l -= 1
    r -= 1
    if r not in d[l].keys():
        d[l][r] = 0
    d[l][r] += 1
for i in range(n-1)[::-1]:
    for k,v in d[i+1].items():
        if k not in d[i]:d[i][k] = 0
        d[i][k] += v
ans = [0]*q
for i in range(q):
    P,Q = map(int,input().split())
    P -= 1
    Q -= 1
    for k,v in d[P].items():
        if k <= Q:
            ans[i] += v
print('\n'.join(str(i) for i in ans))
### BUGGY CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = dict()
for i in range(N):
    dp[i, i + 1] = 0

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        dp[i, j] = min(dp[i, k] + dp[k, j] + acc[j] - acc[i] for k in range(i + 1, j))

print(dp[0, N])


### FIXED CODE ###

# https://atcoder.jp/contests/dp/tasks/dp_n

import itertools as it

INF = 1 << 62
N = int(input())
xs = [int(s) for s in input().split()]
acc = list(it.accumulate([0] + xs))

dp = [[INF] * (N + 1) for _ in range(N)]

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

for w in range(2, N + 1):
    for i in range(N - w + 1):
        j = i + w
        subcost = min(dp[i][k] + dp[k][j] for k in range(i + 1, j))
        dp[i][j] = subcost + acc[j] - acc[i]

print(dp[0][N])