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

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)] # #.のグリッドの場合
#print(a)

from collections import deque
step = [(0,1), (0,-1), (1,0), (-1,0)]
que = deque()

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            seen[i][j] = 0
ans = 0
#import numpy as np
#print(np.array(seen))
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '#':
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '#'
            que.append((xi, yi))
    #print(np.array(seen))
print(ans)




### FIXED CODE ###

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)] # #.のグリッドの場合
#print(a)

from collections import deque
step = [(0,1), (0,-1), (1,0), (-1,0)]
que = deque()

seen = [[-1] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            que.append((i, j))
            seen[i][j] = 0
ans = 0
#import numpy as np
#print(np.array(seen))
while len(que) > 0:
    x, y = que.popleft()
    for tx, ty in step:
        xi, yi = x + tx, y + ty
        if xi < 0 or yi < 0 or xi >= h or yi >= w:
            continue
        if a[xi][yi] == '#':
            continue
        if a[xi][yi] == '.':
            seen[xi][yi] = seen[x][y] + 1
            ans = max(ans, seen[xi][yi])
            a[xi][yi] = '#'
            que.append((xi, yi))
    #print(np.array(seen))
print(ans)
### BUGGY CODE ###

R,G,B,N = map(int,input().split(' '))
list = [R,G,B]
A,B,C = sorted(list)
num = 0
E = int(N//C+1)
F = int(N//B+1)
for i in range(E):
  for j in range(F):
    X = N-C*i-B*j
    if X >= 0  and X % A == 0:
      num += 1
print(num)

### FIXED CODE ###

R,G,B,N = map(int,input().split(' '))
A,B,C = sorted([R,G,B])
if A==1 and B==1 and C ==1:
  print(int((N+2)*(N+1)/2))
  exit()
num = 0
E = int(N//C+1)
F = int(N//B+1)
for i in range(E):
  for j in range(F):
    X = N-C*i-B*j
    if X >= 0  and X % A == 0:
      num += 1
print(num)
### BUGGY CODE ###

from collections import Counter

M = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
prev = Counter()
for i, a in enumerate(A, 1):
  curr = Counter({a+s: c for s, c in prev.items() if a+s<=S})
  curr.update({a:i})
  ans = (ans + curr[S]*(N-i+1))%M
  curr.update(prev)
  prev = curr

print(ans)
    

### FIXED CODE ###

M = 998244353
N, S = map(int, input().split())

ans = 0
prev = [0]*S
for i, a in enumerate(map(int, input().split()), 1):
  if a > S:
    continue
  prev[0] = i
  ans = (ans + prev[S-a]*(N-i+1)) % M
  for j, s in enumerate(prev[:S-a], a):
    prev[j] += s
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra
N = int(input())
abc = [map(int, input().split()) for i in range(N-1)]

Q, K = map(int, input().split())
xy = [map(int, input().split()) for i in range(Q)]

g = [[10**9+1]*N for i in range(N)]

for a, b, c in abc:
    g[a-1][b-1] = c
    g[b-1][a-1] = c

G = csgraph_from_dense(g, null_value=10**9+1)

g2 = dijkstra(G)
for x, y in xy:
    print(int(g2[x-1][K-1] + g2[K-1][y-1]))


### FIXED CODE ###

N=int(input())
abc=[tuple(map(int,input().split())) for i in range(N-1)]
g=[set() for i in range(N)]
for a,b,c in abc:
  g[a-1].add((b-1,c))
  g[b-1].add((a-1,c))
memo=[-1]*N

Q,K=map(int,input().split())
import collections
q=collections.deque([(K-1,0)])
memo[K-1]=0
while(q):
  
  x,w = q.popleft()
  for a,b in g[x]:
    if memo[a]==-1:
      memo[a]=w+b
      q.append((a,w+b))
  
for i in range(Q):
  x,y=map(int,input().split())
  print(memo[x-1]+memo[y-1])
### BUGGY CODE ###

N, A = list(map(int, input().split()))
x = list(map(int, input().split()))
X = max(max(x), A)

dp=[[[0 for k in range(N*X+1)] for j in range(N+1)] for i in range(N+1)]

ans = 0
for j in range(N+1):
  for k in range(N+1):
    for s in range(N*X+1):
      if j==0 and k==0 and s==0:
        dp[j][k][s]=1
      elif j>=1 and s<x[j-1]:
        dp[j][k][s] = dp[j-1][k][s]
      elif j>=1 and k>=1 and s>=x[j-1]:
        dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
      else:
        dp[j][k][s] = 0
      if j==N and s==k*A:
        ans = ans + dp[j][k][s]
print(ans-1)


### FIXED CODE ###

N, A = list(map(int, input().split()))
x = list(map(int, input().split()))
X = max(max(x), A)

dp=[[[0 for k in range(N*X+1)] for j in range(N+1)] for i in range(N+1)]

ans = 0
for j in range(N+1):
  for k in range(N+1):
    for s in range(N*X+1):
      if j==0 and k==0 and s==0:
        dp[j][k][s]=1
      elif j>=1 and s<x[j-1]:
        dp[j][k][s] = dp[j-1][k][s]
      elif j>=1 and k>=1 and s>=x[j-1]:
        dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
      else:
        dp[j][k][s] = 0
      if j==N and s==k*A:
        ans = ans + dp[j][k][s]
print(ans-1)
### BUGGY CODE ###

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

tmp_list = [[0]for i in range(n)]
p_list = []
y_list = []

for i in range(m):
    p,y = map(int,input().split())
    tmp_list[p-1].append(y)
    p_list.append(p)
    y_list.append(y)

import copy
tmpsort = copy.deepcopy(tmp_list)
for i in range(len(tmp_list)):
    tmpsort[i].sort()
for i in range(len(p_list)):
    idx = tmpsort[p_list[i]-1].index(y_list[i])
    print((6-len(str(p_list[i])))*'0' + str(p_list[i]) + (6-len(str(idx)))*'0' + str(idx))

### FIXED CODE ###

N,M = map(int, input().split())  
piys = [[] for _ in range(N)]   
for i in range(M):  
    p, y = map(int, input().split())  
    piys[p-1].append((y,i))  

ans = [None]*M  
for p,iys in enumerate(piys):  
    iys.sort()  
    for k,(y,i) in enumerate(iys):  
        ans[i] = "%06d%06d" % (p+1,k+1)  

for i in ans:  
    print(i)
### BUGGY CODE ###

import itertools
N = int(input())
A = list(map(int, input().split()))
sm=0
mod=10**9+7
for i in itertools.combinations(A,2):
    sm+=i[0]*i[1]
    sm%=mod

print(sm)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
sm=0
mod=10**9+7
s=sum(A)
for i in A:
    s-=i
    sm+=i*s
    sm%=mod
print(sm)
### BUGGY CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
print(max(A[1:]))
for i in range(1,N-1):
    A1 = max(A[:i])
    A2 = max(A[i+1:])
    print(max(A1,A2))
print(max(A[:N-1]))

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
f = max(A)
if A.count(f) >=2:
    for i in range(N):
        print(f)
else:
    M = A.index(f)
    del A[M]
    for i in range(M):
        print(f)
    print(max(A))
    for i in range(M+1,N):
        print(f)
### BUGGY CODE ###

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

flag=1
A,B=0,0
for i in range(n):
    if flag==1:
        AB=sorted(AB, key=lambda x:x[0])
        A +=AB.pop()[0]
        flag *=-1
    else:
        AB=sorted(AB, key=lambda x:x[1])
        B +=AB.pop()[1]
        flag *=-1

print(A-B)

### FIXED CODE ###

n=int(input())
AB=[list(map(int,input().split())) for _ in range(n)]

A,B=[],[]
for i,j in AB:
    A.append(i+j)
    B.append(-j)

ans=sum(B)
A=sorted(A)[::-1]
for i in range(0,n,2):
    ans +=A[i]

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

# coding: utf-8
# Your code here!
n=int(input())
a=[0]
cnt=[0]
ans=True
for i in range(n):
    s=input()
    for j in range(len(a)):
        if a[j]==s:
            cnt[j]+=1
            ans=False
        if ans:
            cnt.append(1)
            a.append(s)
    ans=True
n=int(input())
for i in range(n):
    s=input()
    for j in range(len(a)):
        if a[j]==s:
            cnt[j]-=1

print(max(cnt))

### FIXED CODE ###

s=[input() for _ in range(int(input()))]
t=[input() for _ in range(int(input()))]
cnt=[0]*(len(s)+1)
for i in range(len(s)):
    cnt[i]=s.count(s[i])-t.count(s[i])
print(max(cnt))
### BUGGY CODE ###

n=int(input())
print(0)
la=input()
if la=='Vacant':
  exit()
print(n-1)
ra=input()
if ra=='Vacant':
  exit()
l=0
r=n-1
while true:
  m=(l+r)//2
  print(m)
  s=input()
  if s=='Vacant':
    exit()
  elif (s!=la and (m-l)%2==0) or (s==ra and (m-l)%2==1):
    r=m-1
    ra=s
  else:
    l=m+1
    la=s


### FIXED CODE ###

n=int(input())
def out(t):
  print(t,flush=True)
  s=input()
  if s=='Male':return 0
  elif s=='Female':return 1
  else:exit()
l=0
r=n
f=out(0)
while l+1!=r:
  m=(l+r)//2
  if (m+f)%2==out(m):l=m
  else:r=m
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)

x = int(input())
p_L = [i for i in range(100,106)]


def dfs(ans,next):
    global p_L
    global x
    global stop_memo


    ans += p_L[next]    
    if ans > x:
        return
    elif ans == x:
        print(1)
        exit()
    
    for val in range(0,6):
        dfs(ans,val)


for i in range(0,6):
    dfs(0,i)
print(0)

### FIXED CODE ###

x = int(input())

product = list(range(100,105+1))

dp = [0] * 10**6

dp[0] = 1
for i in product:
    dp[i] = 1

for i in range(0,10**5+1):
    for j in product:
        if dp[i] == 1:
            dp[i+j] = 1

print(dp[x])
### BUGGY CODE ###

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

count = 0
for i in range(n-1):
  for j in range(i+1,n):
    if abs(i - j) == a[i]+a[j]:
      count += 1
      
print(count)

### FIXED CODE ###

import collections

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

l = []
r = []
for i in range(n):
  l.append(i+a[i])
  r.append(i-a[i])

count = collections.Counter(r)
ans = 0
for i in l:
  ans += count.get(i,0)
      
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
AB = []
ans = [0] * (n-1)

for i in range(m):
    AB.append(sorted(map(int,input().split())))
    
AB = sorted(AB)
    
import collections
que = collections.deque()
que.append(1)
    
while que:
    x = que.popleft()
    
    for i in AB:
        a = i[0]
        b = i[1]
        
        if x < a:
            break
        
        if a == x:
            if ans[b-2] == 0:
                ans[b-2] = x
                que.append(b)
        elif b == x:
            if ans[a-2] == 0:
                ans[a-2] = x
                que.append(a)
            
if 0 in ans:
    print("No")
else:
    print("Yes")
    
    for i in ans:
        print(i)

### FIXED CODE ###

n,m = map(int,input().split())
ans = [-1] * n
edge = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    edge[a].append(b)
    edge[b].append(a)
    
import collections
que = collections.deque()
que.append(0)
    
while que:
    x = que.popleft()
    
    for to in edge[x]:
        if ans[to] == -1:
            ans[to] = x + 1
            que.append(to)
            
if -1 in ans[1:]:
    print("No")
else:
    print("Yes")
    print(*ans[1:],sep="\n")
### BUGGY CODE ###

import numpy as np
import sys
input=sys.stdin.readline # for speed up

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

c=[0]*n
for ii in np.arange(1,k):
  hii=h[ii]
  cii=c[0]+abs(hii-h[0])
  for (cjj,hjj) in zip(c[1:ii],h[1:ii]):
    if cii>cjj:
      cii=min(cii,cjj+abs(hii-hjj))
  c[ii]=cii
"""
c[1]=c[0]+abs(h[1]-h[0])
c[2]=min(c[0]+abs(h[2]-h[0]),c[1]+abs(h[2]-h[1]))
c[3]=min(c[0]+abs(h[3]-h[0]),c[1]+abs(h[3]-h[1]),c[2]+abs(h[3]-h[2]))
"""
for ii in np.arange(k,n):
  hii=h[ii]
  cii=c[ii-k]+abs(hii-h[ii-k])
  for (cjj,hjj) in zip(c[ii-k+1:ii],h[ii-k+1:ii]):
    if cii>cjj:
      cii=min(cii,cjj+abs(hii-hjj))
  c[ii]=cii
print(c[n-1])

### FIXED CODE ###

import numpy as np
import sys
input=sys.stdin.readline # for speed up

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

c=[0]*n
kn=np.arange(1,k)
h0=h[0]
c0=c[0]
for (ii,hii) in zip(kn,h[1:k]):
  #hii=h[ii]
  cii=c0+abs(hii-h0)
  for (cjj,hjj) in zip(c[1:ii],h[1:ii]):
    if cii>cjj:
      #cii=min(cii,cjj+abs(hii-hjj))
      if hii==hjj:
        #cii=min(cii,cjj)
        cii=cjj
      elif hii>hjj:
        if cii>cjj+hii-hjj:
          cii=cjj+hii-hjj
      elif cii>cjj-hii+hjj:
        cii=cjj-hii+hjj
  c[ii]=cii
"""
c[1]=c[0]+abs(h[1]-h[0])
c[2]=min(c[0]+abs(h[2]-h[0]),c[1]+abs(h[2]-h[1]))
c[3]=min(c[0]+abs(h[3]-h[0]),c[1]+abs(h[3]-h[1]),c[2]+abs(h[3]-h[2]))
"""
#print(c)
kn=np.arange(k,n)
for (ii,hii,hiik) in zip(kn,h[k:n],h[0:n-k]):
  #hii=h[ii]
  cii=c[ii-k]+abs(hii-hiik)
  for (cjj,hjj) in zip(c[ii-k+1:ii],h[ii-k+1:ii]):
    if cii>cjj:
      #cii=min(cii,cjj+abs(hii-hjj))
      if hii==hjj:
        #cii=min(cii,cjj)
        cii=cjj
      elif hii>hjj:
        if cii>cjj+hii-hjj:
          cii=cjj+hii-hjj
      elif cii>cjj-hii+hjj:
        cii=cjj-hii+hjj
  c[ii]=cii
  #print(c)
print(c[n-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
num = 0
for i in range(1,N+1):
    for j in range(1,N+1):
        if abs(i-j) == A[i-1]+A[j-1]:
            num+=1

print(int(num/2))

### FIXED CODE ###

import collections

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

L = [i + A[i] for i in range(N)]
R = [i - A[i] for i in range(N)]

countL = collections.Counter(L)

countR = collections.Counter(R)


print(sum([countL[n] * countR[n] for n in countL.keys()]))
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1, N+1):
  wi, vi = map(int, input().split())
  for w in range(1, W+1):
    if w - wi < 0:
      dp[i][w] = dp[i-1][w]
    else:
      dp[i][w] = max(dp[i-1][w], dp[i-1][w-wi]+vi)

print(dp[N][W])


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:# 巡回閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=start[0]
ans=[s+1]
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)

print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
### BUGGY CODE ###

import itertools
 
N, K, C = map(int, input().split())
S = input()
 
days = [i+1 for i, x in enumerate(S) if x == 'o']
 
wp = list(itertools.combinations(days,K))
wList =[]
 
for w in wp:
  w = list(w)
  isContinue = False
  for sub in range(len(w)-1):
    if w[sub+1] - w[sub] <= C:
      isContinue = True
  if isContinue == False:
    wList.append(w)
 
#tp = map(tuple, wList)
#qty = map(lambda x: tp.count(x), tuple(tp))
#print(set(wList[1]) & set([6]))
#print(set(wList[1] & set(6)))
 
ans = wList[0]
for i in wList:
  ans = (set(i) & set(list(ans)))
 
ans = sorted(list(ans))
for i in ans:
  print(i)

### FIXED CODE ###

N, K, C = map(int, input().split())
S = input()
S_reverse = S[::-1]

l = []
r = []

i = 0
while i<N and len(l)<K:
    if S[i] == 'o':
        l.append(i+1)
        i += C+1
    else:
        i += 1

i = 0
while i<N and len(r)<K:
    if S_reverse[i] == 'o':
        r.append(i)
        i += C+1
    else:
        i += 1

r = [N - i for i in r]
r.reverse()

ans = []

# print(l)
# print(r)

for i in range(K):
    if l[i] == r[i]:
        ans.append(l[i])


# exit()
# ans = set(l) & set(r)

# ans = list(ans)
ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

from scipy.special import comb

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

# N=2の時は組み合わせは1つしかない
if N == 2:
    print(A[0], A[1])
    exit(0)


A.sort()
n = A[-1]
mid = n//2
idx = 0
ans_abs = 10**9
for i in range(N-1):
    if ans_abs > abs(mid-A[i]):
        ans_abs = abs(mid-A[i])
        idx = i

cmb = comb(n, A[idx], exact=True)
cmb_h = comb(n, A[idx+1], exact=True)
cmb_l = 0
if idx > 0:
    cmb_l = comb(n, A[idx-1], exact=True)

max_cmb = max(cmb, cmb_l, cmb_h)
if cmb == max_cmb:
    print(n, A[idx])
elif cmb_l == max_cmb:
    print(n, A[idx-1])
else:
    print(n, A[idx+1])


### FIXED CODE ###

import bisect

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

A.sort()
n = A[-1]
mid = bisect.bisect(A, n/2)

if abs(n/2-A[mid-1]) > abs(n/2-A[mid]):
    print(n, A[mid])
else:
    print(n, A[mid-1])
### BUGGY CODE ###

import functools
n = int(input())
a_list = list(map(int,input().split()))

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x%y==0:
        return y
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
tmp = []
for i in range(n):
    if a_list[:i]==[]:
        res.append(functools.reduce(gcd, a_list[i+1:]))
    elif a_list[i+1:]==[]:
        res.append(functools.reduce(gcd, a_list[:i]))
    else:
        l_gcd = functools.reduce(gcd, a_list[:i])
        r_gcd = functools.reduce(gcd, a_list[i+1:])
        res.append(gcd(l_gcd,r_gcd))
print(max(res))

### FIXED CODE ###

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y==0:
        return x
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
l_gcd = [0]*(n+2)
r_gcd = [0]*(n+2)
for i in range(n+1):
    if i ==0:
        l_gcd[i] = 0
        r_gcd[n-i+1] = 0
        continue
    l_gcd[i] = gcd(l_gcd[i-1], a_list[i-1])
    r_gcd[n-i] = gcd(r_gcd[n-i+1], a_list[n-i])

for i in range(n+1):
    res.append(gcd(l_gcd[i],r_gcd[i+1]))

print(max(res))
### BUGGY CODE ###

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


flag = True
result=0

for pp in p:
    buf=p[0:pp]
    if min(buf)==p[pp-1]:
        result+=1
        
print(result)
    


### FIXED CODE ###

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


result=0

mm = 10**11

for pp in p:
    if pp <= mm:
        mm=pp
        result+=1

print(result)
### BUGGY CODE ###

N, M, Q = map(int,input().split())

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]

for j in range(Q):
	p,q = map(int,input().split())
	s = 0
	for i in range(p,q+1):
		s += (D[i][q+1] - D[i][i])
	print(s)


### FIXED CODE ###

N, M, Q = map(int,input().split())

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
E = [0 for i in range(N+4)]
F = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]
for i in range(N+1):
	E[i+1] = E[i] + D[i][i]
for i in range(N+2):
	for j in range(N+2):
		F[i+1][j] = F[i][j] + D[i][j]

# C[l][l] + ... + C[l][r] = D[l][r+1] - D[l][l]
# C[i][i] + ... + C[i][r] = D[i][r+1] - D[i][i]
# C[r][r] + ... + C[r][r] = D[r][r+1] - D[r][r]

for j in range(Q):
	p,q = map(int,input().split())
	s = F[q+1][q+1] - F[p][q+1] - (E[q+1] - E[p])
	print(s)
### BUGGY CODE ###

N = int(input())
s = input()

cnt = 0

for i in range(N-2):
    for j in range(i+1, N-1):
        if s[i] == s[j]:
            continue
        for k in range(j+1, N):
            if j-i == k-j:
                continue
            if s[i] == s[k] or s[j] == s[k]:
                continue
            cnt += 1

print(cnt)


### FIXED CODE ###

N = int(input())
s = input()


# for i in range(N-2):
#     for j in range(i+1, N-1):
#         if s[i] == s[j]:
#             continue
#         for k in range(j+1, N):
#             if j-i == k-j:
#                 continue
#             if s[i] == s[k] or s[j] == s[k]:
#                 continue
#             cnt += 1

r = 0
g = 0
b = 0

for t in s:
    if t == "R":
        r += 1
    elif t == "G":
        g += 1

b = N - r - g
cnt = r * g * b

for i in range(1, N-1):
    j = 1
    while 0 <= i-j and i+j <= N-1:
        if s[i] != s[i-j] and s[i] != s[i+j] and s[i-j] != s[i+j]:
            cnt -= 1
        j += 1

print(cnt)
### BUGGY CODE ###

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

a.sort()
a.reverse()

ans = 0
seq = [a[0]]

seq.append(a[1])
ans += a[0]

l = 2
for i in range(2, n):
    pos = 0
    m_ans, M_ans = 0, 0
    for p in range(l):
        np = p + 1
        if np == l:
            np = 0
        m, M = min(seq[p], seq[np]), max(seq[p], seq[np])
        if m >= m_ans and M >= m_ans:
            pos = np
            m_ans = m
            M_ans = M
    ans += m_ans
    seq.insert(pos, a[i])
    l += 1
print(ans)


### FIXED CODE ###

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

a.sort()
a.reverse()

#ans = 0
#seq = [a[0]]
#
#seq.append(a[1])
#ans += a[0]
#
#l = 2
#for i in range(2, n):
#    pos = 0
#    m_ans, M_ans = 0, 0
#    for p in range(l):
#        np = p + 1
#        if np == l:
#            np = 0
#        m, M = min(seq[p], seq[np]), max(seq[p], seq[np])
#        if m >= m_ans and M >= m_ans:
#            pos = np
#            m_ans = m
#            M_ans = M
#    ans += m_ans
#    seq.insert(pos, a[i])
#    l += 1
#print(ans)

ans = 0
cur = 0
cnt = 1
for i in range(n - 1):
    if cnt == 2:
        cur += 1
        cnt = 0
    ans += a[cur]
    cnt += 1
print(ans)