Harryxun/stf_run huggingface dataset:
N = int(input())
A = list(map(int,input().split()))
A = sorted(A)
ans = 0
import heapq
heapq.heapify(A)
while A != []:
    a = heapq.heappop(A)
    ans += 1
    AA = []
    if A[0] == a:
        ans -= 1
    for i in range(len(A)):
        if not (A[i] % a == 0):
            AA.append(A[i])
    A = AA
print(ans)

### FIXED CODE ###

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

s = A[-1]
p = [0 for _ in range(s+1)]
for i in A:
    p[i] += 1
    if p[i] > 1:
        continue
    for j in range(i*2,s+1,i):
        p[j] += 1
ans = 0
for i in A:
    if p[i] == 1:
        ans += 1
print(ans)
N = int(input())
A = [el for el in map(int,input().split())]
if 0 in A : 
    print(0)
    sys.exit(0)
res = 1
for el in A:
  res *= el
  if res - 10**18 > 0:
    print(-1)
    sys.exit(0)
print(res)

### FIXED CODE ###

import sys
N = int(input())
A = [el for el in map(int,input().split())]
if 0 in A : 
    print(0)
    sys.exit(0)
res = 1
for el in A:
  res *= el
  if res - 10**18 > 0:
    print(-1)
    sys.exit(0)
print(res)
N = input()
N = int(N)
s = [[ int(i) for i in input().split()] for i in range(N)]
W = [int(i) for i in input().split()] 


W,H,x,y = (int(i) for i in input().split())
hoge = 0
if W//2 == x and H // 2 == y:
    hoge = 1

print(str(W*H//2) +" " + str(hoge))

### FIXED CODE ###

W,H,x,y = (int(i) for i in input().split())
hoge = 0
if W / 2 == x and H / 2 == y and H > 0 and W > 0:
    hoge = 1

print(str(W*H/2) +" " + str(hoge))
from fractions import gcd
import math
import numpy as np
N = list(map(int, input().split()))
g = gcd(N[0], N[1])

prime = [1]
for i in range(2, g+1):
  while g % i == 0:
    g /= i
    prime.append(i)
print(len(set(prime)))


### FIXED CODE ###

N = int(input())
print((N-N//2)/N)
N = int(input())
S = list(input())
if S[:(N//2) == S[(N//2+1):]:
     print("Yes")
else:
     print("No")

### FIXED CODE ###

N = int(input())
S = input()
if S[:(N//2)] == S[(N//2):]:
	print("Yes")
else:
	print("No")
N = int(input())
str = input()
str_list=list(str)
pre_list=[]
length_list=[]
answer_list=[]
answer_first=0
answer_second=0
for i in range (N-1):
  if str_list[i] != str_list[i+1]:
    pre_list.append(i)
    lenlen=len(pre_list)
for i in range (lenlen-1):
  length_list.append(pre_list[i+1]-pre_list[i])
basyo = length_list.index(max(length_list))
basyo2_kouho1 = pre_list[basyo]
basyo2_kouho2 = pre_list[basyo+1]
for i in range (N):
  if str_list[i] == "E":
    seki = -1
  else:
    seki = 1
  point = (i-basyo2_kouho1)*seki
  if point<0:
    answer_first = answer_first+1
for i in range (N):
  if str_list[i] == "E":
    seki = -1
  else:
    seki = 1
  point = (i-basyo2_kouho2)*seki
  if point<0:
    answer_second = answer_second+1
if answer_first>=answer_second:
  print(answer_second)
else:
  print(answer_first)

### FIXED CODE ###

N = int(input())
str = input()
str_list=list(str)
num_list=[]
ans_list=[]
num=0
for i in range (N):
  if str_list[i]=="E":
    num=num+1
    num_list.append(num)
  else:
    num_list.append(num)
   
for i in range (N):
  if i==0:
    ans=num_list[N-1]-num_list[i]
    ans_list.append(ans)
  else:
    ans=num_list[N-1]-num_list[i]+i-num_list[i-1]
    ans_list.append(ans)

print(min(ans_list))
l=list(map(int,input().split.()))
n=l[0]
w=l[1]
wa=[0]*n
va=[0]*n
for i in range(n):
  ll=list(map(int,input().split.()))
  wa[i]=ll[0]
  va[i]=ll[1]
dp=[[0 for j in range(w+1)] for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,w+1):
    if wa[i-1]<j:
      dp[i][j]=dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-wa[i-1]]+va[i-1])
print(dp[-1][-1])



### FIXED CODE ###

def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))
N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
list_H = sorted(H, reverse=True)
for k in range(K):
    list_H.pop(k)
attack = 0
for i in H:
    attack += i
print(attack)


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
H.sort(reverse=True)
print(sum(H[K:]))
n = int(input())
count = 0
 
for i in n:
  if len(i)%2 != 0:
    count += 1
 
print(count)

### FIXED CODE ###

a,b,c = map(int, input().split())
 
if b+c > a :
  print(c-(a-b))
  
else:
  print(0)
N,K=map(int, input().split())
H=list(map(int, input().split()))

H_sort = sorted(H, reverse=True)

if N <= K:
    print(0)
    quit()
for i in range(K):
    del H_sort[i]

print(sum(H_sort))

### FIXED CODE ###

n, k = map(int, input().split())
h = sorted(map(int, input().split()))
 
x = 0

if n - k <= 0:
    print(0)
else:
    for i in range(n-k):
        x += h[i]
    print(x)
def count(x,y):
    return abs((x-y)/2)

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


if (A-B)%2==0:
    ans=count(A,B)

else:
    
    if (A-1)<(N-B):
        ans=A
        A=1
        B=B-ans
    else:
        ans=N-B+1
        A=A+ans
        B=N
    
    ans+=count(A,B)

print(int(ans))

### FIXED CODE ###

s=input()
k=int(input())

ans=1
for i in range(min(len(s),k)):
    if int(s[i])!=1:
        ans=s[i]
        break

print(ans)
a, b, c, d = [int(input()), for _ in range(4)]
print(min(a,b)+min(c,d))

### FIXED CODE ###

a,b,c,d=[int(input()) for _ in range(4)]
print(min(a,b)+min(c,d))
A,P=map(int,input().split())↲
N=0↲
a=A*3↲
if a>1:
  N=(a+P)//2
elif a==0 and P>1:
  N=P//2
print(N)

### FIXED CODE ###

a, p = map(int, input().split())
#print (int((a*3 + p) / 2))
#a,p=map(int,input().split())↲
print(int((a*3+p)/2))
N = int(input())
A = list(map(int, input().split()))
A.sort()
B = [0] * (2 * 10 ** 5 + 1)
M = max(A)

for a in A:
	B[a] += 1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
M = max(A)
B = [0] * (M + 1)

for a in A:
    B[a] += 1

for a in A:
    if B[a] > 0:
        i = 2
        b = a * i
        while b <= M:
            B[b] = 0
            i += 1
            b = a * i
for i in range(M + 1):
    if B[i] > 1:
        B[i] = 0
print(sum(B))
from collections import defaultdict

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(li, r, s, p):
    v = []

    def f(li, v):
        if len(li) == 0:
            return 0

        score = 0

        # グーを出す時
        if "r" not in v:
            x = "r"
            if li[0] == "s":
                score = max(score, f(li[1:], ["r"]) + r)
            else:
                score = max(score, f(li[1:], ["r"]))

        # チョキを出す時
        if "s" not in v:
            x = "s"
            if li[0] == "p":
                score = max(score, f(li[1:], ["s"]) + s)
            else:
                score = max(score, f(li[1:], ["s"]))

        # パーを出す時
        if "p" not in v:
            x = "p"
            if li[0] == "r":
                score = max(score, f(li[1:], ["p"]) + p)
            else:
                score = max(score, f(li[1:], ["p"]))

        return score
    return f(li, v)


ans = []
for i in range(k):
    ans.append(solve(cir[i], r, s, p))

print(sum(ans))

### FIXED CODE ###

from collections import defaultdict

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = list(map(str, input().rstrip()))

cir = defaultdict(list)
for i in range(k):
    cir[i] = t[i::k]


def solve(sq):
    # 初手
    x = sq[0]
    if x == "r":
        before, score = "r", p
    elif x == "s":
        before, score = "s", r
    else:
        before, score = "p", s
    cnt = 1

    # 前回と違う手なら問答無用で勝てる、前回と同じ手なら奇数回目に勝てる
    for x in sq[1:]:
        if before != x:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            before = x
            cnt = 1
        elif cnt % 2 == 1:
            cnt += 1
        else:
            if x == "r":
                score += p
            elif x == "s":
                score += r
            else:
                score += s
            cnt += 1
    return score


ans = []
for i in range(k):
    ans.append(solve(cir[i]))

print(sum(ans))
s = input()
if s == AAA or BBB:
  print('No')
else:
  print('Yes')

### FIXED CODE ###

s = input()
if s == 'AAA':
  print('No')
elif s == 'BBB':
  print('No')
else: 
  print('Yes')
N = int(input())
T = [[0,0,0]]+[map(int, input().split()) for _ in range(N)]
flag = 'Yes'
i = 0
while flag=='Yes' and i<len(T)-2:
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    i += 1        
print(flag)
    

### FIXED CODE ###

N = int(input())
T = [[0,0,0]]+[ [int(x) for x in input().split()] for _ in range(N)]

flag = 'Yes'
i = 0
while flag=='Yes' and i<len(T)-1:
    t1,x1,y1 = T[i] 
    t2,x2,y2 = T[i+1]
    dis = abs(x2-x1)+abs(y2-y1)
    _t = t2-t1
    if dis > _t or _t%2 != dis%2:
        flag = 'No'
    i += 1        
print(flag)
N,M = map(int,input().split())
import numpy as np
A = sorted(np.array(list(map(int,input().split()))),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>M:
    left=x
  else:
    right=x
ans = 0
for a in A:
  b = max(left-a,1)
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+(sum(A[:c]))
  if M<=0:
    break
  
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse=True)
bi = [0]*(A[0]+1)
for a in A:
  bi[a]+=1
  
cum = [0]*(A[0]+1)
for i in range(1,A[0]+1):
  cum[i]=cum[i-1]+bi[i]

cum_max=cum[-1]
left = 0
right = A[0]*2+1
while right-1!=left:
  x = (right+left)//2
  num = 0
  for a in A:
    b = max(x-a,1)
    if b<=A[0]:
      num += cum_max-cum[b-1]
    
  if num>=M:
    left=x
  else:
    right=x

ans = 0
cum_A = [0]*(N+1)
for i in range(1,N+1):
  cum_A[i]=cum_A[i-1]+A[i-1]
for a in A:
  b = max(right-a,1)
  if b>A[0]:
    break
  c = cum_max-cum[b-1]
  M-=c
  ans+=(a*c)+cum_A[c]
  

ans+=M*left
print(ans)
a = int(raw_input())
b = int(raw_input())

print = (a *  b),(a*2 + b*2)

### FIXED CODE ###

a,b = map(int,raw_input().split())
print ("{0} {1}").format(a*b,2*a+2*b)
N = int(input())
x = []
y = []
for i in range(N):
    a,b = map(int, (input().split()))
    x.append(a)
    y.append(b)
​
aaa = 0
for i in range(N):
    for k in range(N):
        aaa += ((x[i] - x[k])**2+(y[i] - y[k])**2)**0.5
print(aaa/N)

### FIXED CODE ###

N = int(input())
x = []
y = []
for i in range(N):
    a,b = map(int, (input().split()))
    x.append(a)
    y.append(b)
aaa = 0
for i in range(N):
    for k in range(N):
        aaa += ((x[i] - x[k])**2+(y[i] - y[k])**2)**0.5
print(aaa/N)
#include <iostream>
using namespace std;

int m[12][12];

bool valid(int y, int x){
  if(0 <= y && y < 12){
    if(0 <= x && x < 12){
        if(m[y][x] == 1) return true;
    }
  }
  return false;
}

void remove_island(int y, int x) {
  int nx, ny;
  int dx[4] = {1, 0, -1,  0};
  int dy[4] = {0, 1,  0, -1};

  m[y][x] = 0;
  for(int i = 0; i < 4; i++){
    ny = y + dy[i];
    nx = x + dx[i];
    if(valid(ny, nx)) remove_island(ny, nx);
  }
}

int main() {
  char c[12];
  int ans;
  while(1){
    for(int i = 0; i < 12; i++){
      if(!(cin >> c)) return 0;
      for(int j = 0; j < 12; j++){
        m[i][j] = (int)(c[j] - '0');
      }
    }

    ans = 0;
    for(int i = 0; i < 12; i++){
      for(int j = 0; j < 12; j++){
        if(valid(i, j)){
          remove_island(i, j);
          ans++;
        }
      }
    }
    cout << ans << endl;
  }
  return 0;
}

### FIXED CODE ###

def get_map():
  map = []
  while True:
    try:
      tmp = list(raw_input())
      if len(tmp) != 12: break
      map.append(tmp)
    except:
      break
  return map

def remove_island(x, y, map):
  map[x][y] = 0
  move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
  for i, j in move:
    if 0 <= x + i <= 11 and 0 <= y + j <= 11 and map[x + i][y + j] == '1':
      map = remove_island(x + i, y + j, map)
  return map[:]

while True:
  map = get_map()
  if len(map) != 12: break

  count = 0
  for x in range(12):
    for y in range(12):
      if map[x][y] == '1':
        count += 1
        map = remove_island(x, y, map)
  print count
N, M = map(int, input().split())
A = list(map(int, input().split()))

A = sorted(A)[::-1]
a = 0
for i in range(M):
    A[a] = A[a] // 2
    if a > 0:
        if A[a-1] > A[a]:
            a -= 1
    if a+1 <= len(A)-1:
        if A[a] < A[a+1]:
            a += 1
            if A[a] < A[a+1]:
                a += 1
        if a+2 <= len(A)-1:
            if A[a] in [A[a+1], A[a+1]+1]:
                if A[a] < A[a+2]:
                    a += 2

print(sum(A))

### FIXED CODE ###

import heapq

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

for i in range(len(A)):
    A[i] *= -1

heapq.heapify(A)
for _ in range(M):
    x = heapq.heappop(A)
    heapq.heappush(A, (-x//2)*(-1))

print(-sum(A))
s = input()
N = len( s )
K = int( input() )

s_set = set()
for i in range( N - K + 1 ):
  for j in range( 1, K + 1 ):
    t = s[ i : i + j ]
    s_set.add(t)

print( sorted( list( s_set ) )[ K - 1 ] )

### FIXED CODE ###

s = input()
N = len( s )
K = int( input() )

s_set = set()
for j in range( 1, K + 1 ):
  for i in range( N - j + 1 ):
    t = s[ i : i + j ]
    s_set.add(t)

print( sorted( list( s_set ) )[ K - 1 ] )
l,r,d = map(int,input().split())
print(r//d-(l-1)//d))

### FIXED CODE ###

l,r,d = map(int,input().split())
print(r//d-(l-1)//d)
n = int(input())
s = []

geta = 0
for i in range(n):
    a = int(input())
    if a % 10 == 0:
        geta += a
    else:
        s.append(a)

s.sort(reverse=True)

tmp = sum(s)

ruiseki = [tmp]
for i in range(n-1):
    ruiseki.append(ruiseki[-1] - s[i])

ans = 0
def DFS(depth, now):
    global ans
    if depth == n:
        if now%10 != 0:
            ans = max(ans, now)
        return

    if now + ruiseki[depth] <= ans:
        return
    DFS(depth+1, now+s[depth])
    DFS(depth+1, now)
DFS(0,0)
if ans != 0:
    ans += geta
print(ans)

### FIXED CODE ###

n = int(input())
s = []

geta = 0
for i in range(n):
    a = int(input())
    if a % 10 == 0:
        geta += a
    else:
        s.append(a)

n = len(s)
s.sort(reverse=True)

tmp = sum(s)

ruiseki = [tmp]
for i in range(n-1):
    ruiseki.append(ruiseki[-1] - s[i])

ans = 0
def DFS(depth, now):
    global ans

    if depth == n:
        if now%10 != 0:
            ans = max(ans, now)
        return
    if now + ruiseki[depth] <= ans:
        return
    DFS(depth+1, now+s[depth])
    DFS(depth+1, now)
DFS(0,0)
if ans != 0:
    ans += geta
print(ans)
a, b = int[int(i) for i in input().split()]

if a < b:
    print("a < b")

elif a > b:
    print("a > b")

else:
    print("a == b") 

### FIXED CODE ###

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

if a < b:
    print("a < b")

elif a > b:
    print("a > b")

else:
    print("a == b")
def walking():
    x, k, d = map(int, input().split())
    r = 0
    if x > 0 and x > k * d:
        return x - k * d
    elif x < 0 and x < -k * d:
        return x + k * d
    elif x > 0 and x < k * d:
        r = x//d
        if (k - r)%2 == 0:
            return x - r * d
        else:
            return x - (r + 1 ) * d
    elif x < 0 and x < -k * d:
        r = abs(x//d)
        if (k - r)%2 == 0:
            return x + r *d
        else:
            return x + (r + 1 ) * d        
    
loc = walking()
print(abs(loc))

### FIXED CODE ###


def walking():
    x, k, d = map(int, input().split())
    x = abs(x)
    r = 0
    if x > k * d:
        return x - k * d
    else:
        r = x//d
        if (k - r)%2 == 0:
            return x - r * d
        else:
            return abs(x - (r + 1 ) * d)
    
loc = walking()
print(loc)
N = int(input())
A = list(map(int, input().split()))
bottom = sum(A)

if A[0] >= 1 and N <> 1:
  print(-1)
  exit()

ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)


### FIXED CODE ###

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

if A[0] >= 2:
  print(-1)
  exit()

ret = 1
children = 1 - A[0]
bottom -= A[0]
 
for i in range(N):
    children = children * 2 - A[i+1]
    if children <= -1:
      ret = -1
      break
    
    bottom -= A[i+1]
    if children >= bottom:
      children = bottom
    ret += children + A[i+1]
print(ret)
from math import gcd

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

h = True
checker = [0 for _i in range(10**6+1)]
for i in a:
    checker[i] += 1
    if sum(checker[i::i]) > 1:
        h = False
        break
    for j in range(i, 10**6+2, i):
        checker[j] += 1

if h == True:
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

from math import gcd

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

checker = [0 for _i in range(10**6+1)]
for i in a:
    checker[i] += 1

if all(sum(checker[i::i])<2 for i in range(2,10**6+1)):
    print('pairwise coprime')
else:
    r = a[0]
    for i in a:
        r = gcd(r, i)
    if r == 1:
        print('setwise coprime')
    else:
        print('not coprime')
import sys
n=int(input())
r=list(map(int,sys.stdin.read())
print(max([max(r[i+1:])-r[i]for i in range(n-1)]))

### FIXED CODE ###

import sys
def f():
 s=1e10;b=-s
 input()
 for r in map(int,sys.stdin):
  if b<r-s:b=r-s
  if s>r:s=r
 print(b)
f()
mod = 10 ** 9 + 7
cnt = [0] * 3
N = int(input())
A = list(map(int,input().split()))

ans = 1
for i in range(N):
    ans *= cnt.count(A[i])
    ans %= mod
    cnt[cnt.index(A[i])] += 1

print(ans)

### FIXED CODE ###

mod = 10 ** 9 + 7
cnt = [0] * 3
N = int(input())
A = list(map(int,input().split()))

ans = 1
for i in range(N):
    ans *= cnt.count(A[i])
    ans %= mod
    if ans == 0:
        break
    cnt[cnt.index(A[i])] += 1

print(ans)
N, K = map(int, input().split())
S = input()

tmp_count = 1
count_list = []
for i in range(N-1):
    if S[i] == "0" and S[i+1] == "0":
        tmp_count += 1
    elif S[i] == "1" and S[i+1] == "1":
        tmp_count += 1
    elif S[i] == "0" and S[i+1] == "1":
        count_list.append(tmp_count)
        tmp_count = 1
    elif  S[i] == "1" and S[i+1] == "0":
        count_list.append(tmp_count)
        tmp_count = 1
count_list.append(tmp_count)

print("countlist =", count_list)

count_sakadati = 0
tmp_list = []
if S[0] == "0":
    for i in range(K):
        tmp_max = 0
        tmp_max_num = 1
        for j in range(0, len(count_list)-1, 2):
            if j == 0:
                tmp_max = count_list[j] + count_list[j+1]
                tmp_max_num = j
            else:
                count_list[j- 1] + count_list[j] + count_list[j+1] > tmp_max
                tmp_max = count_list[j- 1] + count_list[j] + count_list[j+1]
                tmp_max_num = j
        if tmp_max_num == 0:
            del count_list[0]
            del count_list[1]
            count_list.insert(0, tmp_max)
        else:
            del count_list[tmp_max_num-1]
            del count_list[tmp_max_num-1]
            del count_list[tmp_max_num-1]
            count_list.insert(tmp_max_num-1, tmp_max)
else:
    for i in range(K):
        tmp_max = 0
        tmp_max_num = 1
        for j in range(1, len(count_list)-1, 2):
            if count_list[j- 1] + count_list[j] + count_list[j+1] > tmp_max:
                tmp_max = count_list[j- 1] + count_list[j] + count_list[j+1]
                tmp_max_num = j
        del count_list[tmp_max_num-1]
        del count_list[tmp_max_num-1]
        del count_list[tmp_max_num-1]
        count_list.insert(tmp_max_num-1, tmp_max)
            
print(max(count_list))

### FIXED CODE ###

N, K = map(int, input().split())
S = input()

bl = []
if S[0] == "0":
    bl.append(0)
bl.append(0)
for i in range(1, N):
    if S[i-1] != S[i]:
        bl.append(i)
bl.append(N)
bl.append(N)

nbl = len(bl)
m = [bl[i+2 * K+1] - bl[i] 
     for i in range(nbl - 2*K-1) if i%2 == 0]
if len(m) == 0:
    print(N)
else:
    print(max(m))
N=input()
i=(int(N[:-3])+1)*1000
j=i-int(N)

if j==1000:
  print(0)
else:
  print(j)

### FIXED CODE ###

N=input()
if len(N)>3:
    i=(int(N[:-3])+1)*1000
else:
    i=1000

j=i-int(N)

if j>999:
  print(0)
else:
  print(j)
N = int(input())
NA = int(input())
NX = NA.split(" ")
NW = []
for i in range (1,N+1):
    Ni = int(NX.count(i))
    NW.append(Ni)
NN = NW.sort()
print(NW)
S = 0
for x in range (0,N-2):
    S = S + NW[x]
print(S)

### FIXED CODE ###

X = input()
Xn = X.replace("1","N")
Xo = Xn.replace("9","1")
print(Xo.replace("N","9"))
n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
ans = 1
cir = 0
a = 0
for i in range(n):
  sub[i] = ans
  if A[ans-1] in sub:
    a = sub.index(A[ans-1])
    cir = i+1 - a
    break
  else:
    ans = A[ans-1]
if sub[-1] != 0:
  print(sub[k%n])
  exit(0)
print(sub[a + (k - a) % cir])

### FIXED CODE ###

S = list(input())
T = list(input())

for i in range(len(S)):
  if T[i] != S[i]:
    print('No')
    exit(0)
print('Yes')
w = input()
cnt = 0
while(True):
    t = input()
    if t == "END_OF_TEXT":
        break
    t = list(map(lower(), t.split()))
    for i in t:
        if i == w:
            cnt += 1
print(cnt)


### FIXED CODE ###

w = input()
cnt = 0
while(True):
    t = input()
    if t == "END_OF_TEXT":
        break
    t = t.lower().split()
    for i in t:
        if i == w:
            cnt += 1
print(cnt)
a = int(input())
x = list(map(int, input().split()))
x.sort()
x = x[::-1]
if a %2 == 0:
  for i in range(1,a,2):
    if not i == x[-1] and i ==x[-2]:
      x.pop()
      x.pop()
      print(0)
      break
  else:print(2**(a//2))
else:
  for i in range(0,a,2):
    x.pop()
    if not i == x[-1] and i ==x[-2]:
      x.pop()
      x.pop()
      print(0)
      break
  else:print(2**(a//2))


### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]

A.sort()
B = [abs(a-b) for a,b in zip(range(N-1,-1,-1),range(N))]
B.sort()

if A==B:
    print(pow(2,N//2,10**9+7))
else:
    print(0)