Harryxun/stf_run huggingface dataset:
def gcd(a,b):
  if a>b:
    a,b = b,a
  if a==1:
    return a
  else:
    return gcd(b%a,a)

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

ans = A[1]
g = A[0]

for i in range(N):
  g = gcd(g,A[i])
  ans = max(ans,g)
print(ans)

### FIXED CODE ###

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

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

from collections import defaultdict

L = defaultdict(lambda :1)
R = defaultdict(lambda :1)
L[1] = A[0]
R[1] = A[N-1]

for i in range(2,N):
  L[i] = gcd(L[i-1],A[i-1])
  R[i] = gcd(R[i-1],A[N-i])

ans = max(L[N-1],R[N-1])
for i in range(1,N-1):
  ans = max(ans,gcd(L[i],R[N-1-i]))

print(ans)
def main():
	l,r,d = map(int,input().split())
    total = 0
    for i in range(l,r+1):
      if i%d == 0:
        total += 1
    
    print(total)
  
  
main()

### FIXED CODE ###

def main():
    l,r,d = map(int,input().split())
    total = 0
    for i in range(l,r+1):
        if i%d == 0:
            total += 1

    print(total)
    

main()
A = int(input())
B = int(input())

def takahashi:
  if A and B >= 1
  	if A and B <= 9
    
    else print('-1')
    	print(A * B)
      

### FIXED CODE ###

A, B = map(int, input().split())
 
if A < 10 and B < 10:
    print(A*B)
else:
    print(-1)
#!/usr/bin/env python
# coding: utf-8

# In[1]:


import sys
#import numpy as np
#import itertools
input = sys.stdin.readline
N, K = map(int, input().split())
V = list(map(int, input().split()))


# In[2]:


#print(N, K)
#print(V)


# In[ ]:


"""
6 4
-10 8 2 1 2 6
"""


# In[29]:


if N < K:
    scs = []
    for i in range(K-N):
        scs.append(sorted(V[i:]))
    s = max(scs)
else:
    scs = []
    for i in range(K//2):
        #print("{}個返す".format(i))
        scss = []
        for j in range(K+1-i):
            #print("左から{}個　右から{}個/{}".format(j,K-j-i, K-i))
            if j == K-i:
                choices = V[:j]
            else:
                choices = V[:j] + V[-K+j+i:]
            #print(choices)
            #print(sorted(choices)[i:])
            scss.append(sum(sorted(choices)[i:]))
        scs.append(max(scss))
    s = max(scs)
    s = 0 if s<0 else s
print(s)


# In[ ]:






### FIXED CODE ###

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

# In[30]:


import sys
#import numpy as np
#import itertools
input = sys.stdin.readline
N, K = map(int, input().split())
V = list(map(int, input().split()))


# In[36]:


#print(N, K)
#print(V)


# In[ ]:


"""
6 4
-10 8 2 1 2 6
"""


# In[46]:


ans = 0
for l in range(K+1):
    if l > N:
        continue
    for r in range(K+1-l):
        if l+r>K or l+r>N:
            continue
        d = K-(l+r)
        picked = V[:l] + V[-r:] if r != 0 else V[:l]
        #print("l:{}, r:{}, picked{}".format(l, r, picked))
        sp = sorted(picked)
        now = sum(picked)
        #print(sp)
        for i in range(d):
            if i >= len(picked):
                break
            if sp[i] > 0:
                break
            now -= sp[i]
        ans = max(ans, now)
print(ans)
        
"""
if N < K:
    scs = []
    for i in range(K-N):
        scs.append(sorted(V[i:]))
    s = max(scs)
else:
    scs = []
    for i in range(K//2):
        #print("{}個返す".format(i))
        scss = []
        for j in range(K+1-i):
            #print("左から{}個　右から{}個/{}".format(j,K-j-i, K-i))
            if j == K-i:
                choices = V[:j]
            else:
                choices = V[:j] + V[-K+j+i:]
            #print(choices)
            #print(sorted(choices)[i:])
            scss.append(sum(sorted(choices)[i:]))
        scs.append(max(scss))
    s = max(scs)
    s = 0 if s<0 else s
print(s)
"""


# In[ ]:
# coding:utf-8

import sys
from collections import Counter, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N = I()
A = [I() for _ in range(N)]

A.sort()
B = deque()

state = 1
for i in range(N // 2):
    if state:
        B.append(A[i])
        B.appendleft(A[-(i + 1)])
    else:
        B.append(A[-(i + 1)])
        B.appendleft(A[i])
    state ^= 1
if N % 2:
    C = deque(B)
    B.append(A[N // 2])
    C.appendleft(A[N // 2])

ans1 = 0
ans2 = 0
for i in range(N - 1):
    ans1 += abs(B[i] - B[i + 1])
    ans2 += abs(C[i] - C[i + 1])

print(max(ans1, ans2))


### FIXED CODE ###

# coding:utf-8

import sys
from collections import Counter, deque

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


N = I()
A = [I() for _ in range(N)]

A.sort()
B = deque()

state = 1
for i in range(N // 2):
    if state:
        B.append(A[i])
        B.appendleft(A[-(i + 1)])
    else:
        B.append(A[-(i + 1)])
        B.appendleft(A[i])
    state ^= 1
if N % 2:
    C = deque(B)
    B.append(A[N // 2])
    C.appendleft(A[N // 2])
else:
    C = A[:]

ans1 = 0
ans2 = 0
for i in range(N - 1):
    ans1 += abs(B[i] - B[i + 1])
    ans2 += abs(C[i] - C[i + 1])

print(max(ans1, ans2))
S,T=input()
a=0
for i in range(len(S)):
  if S[i]!=T[i]:
    a+=1
if a==0:
  print("Yes")
else:
  print("No")

	
  


### FIXED CODE ###

S=input()
T=input()
a=0
for i in range(len(S)):
  if S[i]!=T[i]:
    a+=1
if a==0:
  print("Yes")
else:
  print("No")
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(100000)

def dfs(x, y, sym):
	tile[x][y] = '.'
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if nx>=0 and nx<N and ny>=0 and ny<M and tile[nx][ny]==sym:
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			if not tile[i][j] == '.':
				if tile[i][j] == '@':
					dfs(i, j, '@')
					res += 1
				elif tile[i][j] == '#':
					dfs(i, j, '#')
					res += 1
				elif tile[i][j] == '*':
					dfs(i, j, '*')
					res += 1
	return res
	
res=0	
counter=0
DX = [-1, 0, 1, 0]
DY = [0, -1, 0, 1]
while True:
	counter+=1
	line = input()
	if ' ' in line:
		nums = line.split(' ')
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(N)]for j in range(M)]
		if N==0 and M==0:
			break
	else:
		tile[counter-2] = list(line)
	if (counter-1)==M:
		res = solve()
		counter = 0
		print(res)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
def dfs(x, y, sym):
	tile[x][y] = "."
	for i in range(len(DX)):
		nx = x + DX[i]
		ny = y + DY[i]
		if (0<=nx and nx<N and 0<=ny and ny<M and tile[nx][ny] is sym):
			dfs(nx, ny, sym)

def solve():
	res = 0
	for i in range(N):
		for j in range(M):
			sym = tile[i][j]
			if tile[i][j] != ".":
				if tile[i][j] is sym:
					dfs(i, j, sym)
					res += 1
	print(res)

counter=0
DX = [-1,0,1,0]
DY = [0,-1,0,1]
sys.setrecursionlimit(10**7)
while True:
	line = input()
	if " " in line:
		nums = line.split(" ")
		N = int(nums[0])
		M = int(nums[1])
		tile = [[0 for i in range(M)] for j in range(N)]
	else:
		tile[counter-1] = list(line)
	if N is 0 and M is 0:
		break
	counter += 1
	if counter-1 is N:
		solve()
		counter = 0
def main():
    input = sys.stdin.readline
    n = int(input())
    nums_table = defaultdict(int)
    ans = 0
    for i in range(1, n+1):
        nums_table[i] = 2
    nums_table[1] = 1
    for i in range(2, n//2+1):
        for j in range(2*i,n+1,i):
            nums_table[j] += 1
    for i in range(1, n+1):
        ans += i * nums_table[i]
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    nums_table = [2] * (n+1)
    ans = 0
    for i in range(1, n+1):
        nums_table[i] = 2
    nums_table[1] = 1
    for i in range(2, n//2+1):
        for j in range(2*i,n+1,i):
            nums_table[j] += 1
    for i in range(1, n+1):
        ans += i * nums_table[i]
    print(ans)
if __name__ == "__main__":
    main()
#include<iostream>

using namespace std;

int main()
{
    int a,b,c;

    cin >> a >> b >> c;

    if(a <= c && c <= b)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    
}

### FIXED CODE ###

a,b,c = map(int,input().split())
print("Yes" if a<=c<=b else "No")
n = int(input())
s = str(input())
if n % 2 !=0:
  print('No')
else:
  if s[0:n/2-1] == s[n/2:n-1]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n = int(input())
s = str(input())
if n % 2 !=0:
  print('No')
else:
  if s[0:int(n/2)] == s[int(n/2):int(n)]:
    print('Yes')
  else:
    print('No')
# C - GeT AC
N, Q = map(int, input().split())
S = str(input())
A = [list(map(int, input().split())) for i in range(Q)]
S1 = [0]*N
count = 0
for j in range(len(S)):
    if S[j] == 'A' and S[j + 1] == 'C':
        count = +1
        S1[j] = count
    else:
        pass
for k in range(Q):
    print(sum(S1[A[k][0]-1:A[k][1]-1]))


### FIXED CODE ###

# C - GeT AC
N, Q = map(int, input().split())
S = str(input())
A = [list(map(int, input().split())) for i in range(Q)]
S1 = [0]*N
count = 0
for j in range(1,len(S)):
    if S[j] == 'C' and S[j - 1] == 'A':
        count += 1
    else:
        pass
    S1[j] = count
#print(S1)

for k in range(Q):
    print(S1[A[k][1]-1]-S1[A[k][0]-1])
s = list(input())
N = len(s)
if N == 1:
    print (0)
    exit()

    ans = 99
for i in range(1, N): #残す文字数
    tmp = 0 #残す文字以外の最大連続数
    count = 0 #残す文字以外が何文字続いているかをカウント
    for j in range(i):
        if s[j] == s[i]:
            tmp = max(tmp, count)
            count = 0
        else:
            count += 1
    tmp = max(tmp, count)
    ans = min(ans, max(tmp, N - i - 1))

print (ans)

### FIXED CODE ###

s = list(input())
N = len(s)
if N == 1:
    print (0)
    exit()

ans = 99
for i in range(1, N): #残す文字数
    tmp = 0 #残す文字以外の最大連続数
    count = 0 #残す文字以外が何文字続いているかをカウント
    for j in range(i):
        if s[j] == s[i]:
            tmp = max(tmp, count)
            count = 0
        else:
            count += 1
    tmp = max(tmp, count)
    ans = min(ans, max(tmp, N - i - 1))

print (ans)
n=int(input())
a=list(map(int,input().split())
print(max(a)-min(a))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
print(max(a)-min(a))
def isPrime(n):
    if (n > 2 and n % 2 == 0) return False
    i = 3
    while (i <= mySqrt(n)):
        if (n % i == 0):
            return false
        i += 2;
    return n > 1


n = int(input())
while !isPrime(n):
  n += 1
print(n)


### FIXED CODE ###

from math import sqrt


def isPrime(n):
    if n > 2 and n % 2 == 0: return False
    i = 3
    while i <= sqrt(n):
        if n % i == 0:
            return False
        i += 2
    return n > 1


n = int(input())
while not isPrime(n):
    n += 1
print(n)
s = input()
k = int(input())
i = 0
while s[i] == '1':
    i += 1
if k < i:
    print(1)
else:
    print(s[i])


### FIXED CODE ###

s = input()
k = int(input())
if len(set(s)) == 1 and s[0] == '1':
    print(1)
else:
    i = 0
    while i < len(s) and s[i] == '1':
        i += 1
    if k <= i:
        print(1)
    else:
        print(s[i])
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    ////find函数返回类型 size_type
    string s,r;
    string::size_type position;
    //find 函数 返回jk 在s 中的下标位置
    cin>>s;
    position = s.find('C');
    if (position == s.npos)  //如果没找到，返回一个特别的标志c++中用npos表示，我这里npos取值是4294967295，
    {
        cout<<"No";
        return 0;
    }
   	position = s.find('F');
   	if (position == s.npos) {
   		cout<<"No";
   		return 0;
	   }
	cout<<"Yes";
}

### FIXED CODE ###

def main():
    s = input()
    if s.count('C') == 0 or s.count('F') == 0:
        print('No')
        return
    l = len(s)
    s = s[s.find('C'):]
    if s.count('F') == 0:
        print('No')
    else:
        print('Yes')
main()
s = input()
t = input()
s.sort()
t.sort(reverse = True)
if s < t:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

s = list(input())
t = list(input())
s.sort()
t.sort(reverse = True)
if s < t:
  print("Yes")
else:
  print("No")
N,A,B=map(int, input().split())
D=list(map(int, input().split()))
D=sorted(D)[::-1]
import math
from math import comb
print(sum(D[:A])/A)
ans=0
if D[0]==D[-1]:
  n=D.count(D[A-1])
  k=V[:A].count(D[A-1])
  print(comb(n,k))
else:
  ans=0
  n=D.count(D[A-1])
  for i in range(A,min(n,B)+1):
    ans+=comb(n,i)
  print(ans)

### FIXED CODE ###

N,A,B=map(int, input().split())
D=list(map(int, input().split()))
D=sorted(D)[::-1]
import math
from math import comb
print(sum(D[:A])/A)
ans=0
if D[0]!=D[A-1]:
  n=D.count(D[A-1])
  k=D[:A].count(D[A-1])
  print(comb(n,k))
else:
  ans=0
  n=D.count(D[A-1])
  for i in range(A,min(n,B)+1):
    ans+=comb(n,i)
  print(ans)
n, k = [int(x) for x in input().split()]

while n > abs(n-k):
    n = abs(n-k)
    if k == 1:
        n = 0
        break
    elif n%k == 0:
        n = 0
        break


print(n)

### FIXED CODE ###

A, B, C = input().split()

temp = A
A = B
B = temp

temp = A
A = C
C = temp

print(A,B,C)
import math

n = int(input())
s = []
for i in range(n):
    s.append(list(str(input())))
    
for i in s:
    i.sort()

s.sort()

tmp = 'a'
total = 0
for i in s:
    if i == tmp:
        cnt += 1
    elif cnt >= 2:
        total += math.factorial(cnt)*math.factorial(cnt-2)/2
        cnt = 1
    tmp = i

print(int(total))

### FIXED CODE ###

n = int(input())
ss = ["".join(sorted(list(input()))) for _ in range(n)]
ss.sort()

ans = 0
cnt = 0
tmp = ss.pop(0)
for s in ss:
    if tmp == s:
        cnt+=1
    elif cnt > 0:
        tmp = s
        ans+=((cnt+1) * cnt // 2)
        cnt = 0
    else:
        tmp = s
        cnt = 0
print(ans + ((cnt+1) * cnt // 2))
_ = input()
seq = list(map(int,input().split()))
 
seq1 = seq[::2]
seq2 = seq[1::2]
 
if len(set(seq)) == 1:
    print(len(seq2))
    exit()
    
def count_dictonary(seq):
    ret_dict={}
    for item in seq:
        if item not in ret_dict:
            ret_dict[item] = 1
        else:
            ret_dict[item]+=1
    return ret_dict
 
def modes(counting_dict):
    #(11,2),(2,1),(3,3)
    ret={}
    for item in counting_dict.items():
        no, count = item
        if counting_dict[no] in ret:
            ret[count].append(no)
        else:
            ret[count]=[no]
            
    return ret
 
 
counting1 = count_dictonary(seq1)
counting2 = count_dictonary(seq2)
 
modes1 = sorted(modes(counting1).items(),reverse=True)
modes2 = sorted(modes(counting2).items(),reverse=True)
 
min_change=len(seq)
if modes1[0][1] != modes2[0][1]:
    min_change = (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[0][0])
else:
    m01=len(seq)
    m10=len(seq)
    #if len(modes2) !=1:
    m01 =  (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[1][0])
    #if len(modes1) !=1:
    m10 =  (len(seq1) - modes1[1][0]) + (len(seq2) - modes2[0][0])
    min_change = min(m01,m10)
    
print(min_change)

### FIXED CODE ###

_ = input()
seq = list(map(int,input().split()))
 
seq1 = seq[::2]
seq2 = seq[1::2]
 
if len(set(seq)) == 1:
    print(len(seq2))
    exit()
    
def count_dictonary(seq):
    ret_dict={}
    for item in seq:
        if item not in ret_dict:
            ret_dict[item] = 1
        else:
            ret_dict[item]+=1
    return ret_dict
 
def modes(counting_dict):
    #(11,2),(2,1),(3,3)
    ret={}
    for item in counting_dict.items():
        no, count = item
        if counting_dict[no] in ret:
            ret[count].append(no)
        else:
            ret[count]=[no]
            
    return ret
 
 
counting1 = count_dictonary(seq1)
counting2 = count_dictonary(seq2)
 
modes1 = sorted(modes(counting1).items(),reverse=True)
modes2 = sorted(modes(counting2).items(),reverse=True)
 
min_change=len(seq)
if modes1[0][1] != modes2[0][1] or len(modes1[0][1]) >=2 or len(modes2[0][1]) >=2:
    min_change = (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[0][0])
else:
    m01=len(seq)
    m10=len(seq)
    if len(modes2) !=1:
        m01 =  (len(seq1) - modes1[0][0]) + (len(seq2) - modes2[1][0])
    if len(modes1) !=1:
        m10 =  (len(seq1) - modes1[1][0]) + (len(seq2) - modes2[0][0])
    min_change = min(m01,m10)
    
print(min_change)
one=list(input())
#print(one)
two=list(input())

for num,i in enumerate(one):
    if i not in z:
        z[i]=[num]
    else:
        z[i].append(num)
p={}
for num,i in enumerate(two):
    if i not in p:
        p[i]=[num]
    else:
        p[i].append(num)
w=[]
#print(p)
#print(z)
for k,v in z.items():
    w.append(v)
o=[]
for k,v in p.items():
    o.append(v)
print("Yes") if w==o else print("No")

### FIXED CODE ###

def main():
    data0 = input()
    data1 = input()

    flag = True
    data_tmp = data0
    count = 0
    len_data = len(data0)
    while True:
        if data0 == "":
            break

        data0 = data0.replace(data0[0], "")
        data1 = data1.replace(data1[0], "")

        if len(data0) != len(data1):
            print('No')
            exit()

    print('Yes')

if __name__ == "__main__":
    main()
n,m = map(int,input().split())
s = []
c = []
for i in range(m):
    val1,val2 = map(int,input().split())
    s.append(val1)
    c.append(val2)

digit = max(s)

ans = []

if digit == 1:
    for i in range(10):
        num = str(i)
        flg = 0
        for j in range(m):
            if num[s[j] - 1] == str(c[j]):
                flg = 1
            else:
                flg = 0
                break
        if flg == 1:
            ans.append(i)
else:
    for i in range(10 ** (digit - 1), 10 ** digit):
        num = str(i)
        flg = 0
        for j in range(m):
            if num[s[j] - 1] == str(c[j]):
                flg = 1
            else:
                flg = 0
                break
        if flg == 1:
            ans.append(i)

if ans:
    print(min(ans))
else:
    print(-1)

### FIXED CODE ###

n,m = map(int,input().split())
s = []
c = []
for i in range(m):
    val1,val2 = map(int,input().split())
    s.append(val1)
    c.append(val2)

for i in range(1000):
    if len(str(i)) == n:
        flg = True
        for j in range(m):
            if int(str(i)[s[j] - 1]) != c[j]:
                    flg = False
        if flg:
            print(i)
            break
if not flg:
    print(-1)
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    H,W,K = map(int, sysread().split())
    S = []
    for i in range(H):
        S.append(list(accumulate(list(map(int, list(input()))), lambda x,y:x+y)))
    for h in range(1, H):
        for w in range(W):
            S[h][w] += S[h-1][w]

    ret = float('inf')

    for idxes_ in product((0,1), repeat=H-1):
        l = 0
        r = 1
        idxes = [0]
        for i, val in enumerate(idxes_, 1):
            if val == 1:
                idxes.append(i)
        idxes.append(H)
        min_cut = len(idxes) - 2
        while r <= W:
            for i in range(len(idxes)-1):
                if idxes[i] == 0 and l == 0:
                    cri = S[idxes[i+1]-1][r-1]
                elif l == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1]
                elif idxes[i] == 0:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i+1]-1][l-1]
                else:
                    cri = S[idxes[i+1]-1][r-1] - S[idxes[i]-1][r-1] - S[idxes[i+1]-1][l-1] + S[idxes[i]-1][l-1]

                if cri > K:
                    r -= 1
                    if l == r:
                        min_cut = float('inf')
                        r = W+1
                        break
                    l = r
                    min_cut += 1
                    break
            r += 1
        ret = min(ret, min_cut)

    print(ret)




if __name__ == "__main__":
    run()


### FIXED CODE ###

# coding: utf-8
from itertools import combinations as combs

H,W,K = list(map(int, input().split()))
arr = []
for i in range(H):
  arr.append(list(map(int, list(input()))))

def cut_sum(arr, x1, x2, y):
  ret = 0
  for i in range(x1, x2):
    ret += arr[i][y]
  return ret

row_idxes = list(range(1,H))
min_val = float('inf')

for n_rows in range(H):
  for row_set in combs(row_idxes, n_rows):
    count = len(row_set)
    row_lines = [0] + list(row_set)+ [H]
    col1, col2 = 0, 1
    sums = [0] * (len(row_lines) - 1)
    while col2 <= W:
      row1 = 0
      for box, row2 in enumerate(row_lines[1:]):
        sums[box] += cut_sum(arr, row1, row2, col2-1)
        if sums[box] > K:
          if (col2 - col1) == 1:
            count = float('inf')
            break
          count += 1
          col1 = col2 - 1
          col2 -= 1
          sums = [0] * (len(row_lines) - 1)
          break
        row1 = row2
      if count >= min_val:
        break
      col2 += 1
    
    if min_val > count:
      min_val = count
print(min_val)
import itertools
import sys
from collections import defaultdict
import bisect

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(input())
left = list(map(int, input().split()))

indices = defaultdict(list)
for i, x in enumerate(left):
    indices[x].append(i)


def dp(t, n1, n2, n3):
    cached = t.get((n1, n2, n3))
    if cached is not None:
        return cached
    remaining = n1 + n2 + n3
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    res = 0
    if last_cnt == n1:
        res += dp(t, n1 - 1, n2, n3)
        res %= M
    if last_cnt == n2:
        res += dp(t, n1, n2 - 1, n3)
        res %= M
    if last_cnt == n3:
        res += dp(t, n1, n2, n3 - 1)
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[n1, n2, n3] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = len(indices[i])
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    assert sum(h) == N
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, h[0], h[1], h[2])
    return res * len(set(itertools.permutations(h))) % M


print(solve())


### FIXED CODE ###

import itertools
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 9)
M = 1000000007
N = int(sys.stdin.readline())
left = list(map(int, sys.stdin.read().split()))
counter = Counter(left)


def dp(t, ns):
    cached = t.get(ns)
    if cached is not None:
        return cached
    remaining = sum(ns)
    assert remaining > 0
    last_cnt = left[remaining - 1] + 1
    n1, n2, n3 = ns
    res = 0
    if last_cnt == n1:
        res += dp(t, tuple(sorted([n1 - 1, n2, n3])))
        res %= M
    if last_cnt == n2:
        res += dp(t, tuple(sorted([n1, n2 - 1, n3])))
        res %= M
    if last_cnt == n3:
        res += dp(t, tuple(sorted([n1, n2, n3 - 1])))
        res %= M
    # print(f"{remaining}: ({n1},{n2},{n3}) => {res}")
    t[ns] = res
    return res


def solve():
    h = [0, 0, 0]
    for i in range(N):
        k = counter[i]
        if k == 3:
            h[0] = h[1] = h[2] = i + 1
        elif k == 2:
            h[0] = h[1] = i + 1
        elif k == 1:
            h[0] = i + 1
        else:
            break
    if sum(h) != N:
        return 0
    t = dict()
    t[0, 0, 0] = 1
    res = dp(t, tuple(sorted(h)))
    return (res * len(set(itertools.permutations(h)))) % M


print(solve())
N = int(input())
for x in range(1, 50_000):
    if int(x * 1.08) == N:
        print(x)
        exit()
print(":(")


### FIXED CODE ###

N = int(input())
for x in range(1, 50000):
    if int(x * 1.08) == N:
        print(x)
        exit()
print(":(")