Harryxun/stf_run huggingface dataset:
#####segfunc######
def segfunc(x,y):
    if x == y == None:
        return []
    if x == None:
        return y
    if y == None:
        return x
    return x | y
def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=set([init_val[i]])   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return []
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
n = int(input())
s = list(input())
ide_ele = None
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
init(s)
for i in range(int(input())):
    a,b,c = input().split()
    if a == "1":
        update(int(b)-1, set([c]))
    else:
        if b == c:
            print(1)
        else:
            print(len(query(int(b)-1,int(c))))

### FIXED CODE ###

import sys
input = sys.stdin.readline
#####segfunc######
def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
n = int(input())
s = list(input())[:-1]
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
s = [2 ** (ord(i) - ord('a')) for i in s]
init(s)
q = int(input())
for i in range(q):
    tmp = input()
    a,b,c = tmp[:-1].split()
    if a == "1":
        update(int(b)-1, 2 ** (ord(c) - ord('a')))
    else:
        if b == c:
            print(1)
        else:
            tmp = query(int(b)-1, int(c))
            tmp = format(tmp, 'b')
            print(tmp.count('1'))
while True:
    (H, W) = [int(i) for i in input().split()]
    if H == W == 0:
       break
 
    for a in range(H):
        for b in range(W):
            print('#', end='')
        print()
    print()

### FIXED CODE ###

import sys
(W, H, x, y, r) = [int(i) for i in sys.stdin.readline().split()]
if r <= x <= W - r and r <= y <= H - r:
    print("Yes")
else:
    print("No")
n = int(input())

for i in range(0, n):
    a = int(input())
    b = int(input())
    if len(str(a + b)) >= 80
        print("overflow")
    elif len(str(a)) >= 80:
        print("overflow")
    elif len(str(b)) >= 80
        print("overflow")
    else :
        print(a + b)

### FIXED CODE ###

n = int(input())

for i in range(0, n):
    a = int(input())
    b = int(input())
    if len(str(a + b)) > 80:
        print("overflow")
    elif len(str(a)) > 80:
        print("overflow")
    elif len(str(b)) > 80:
        print("overflow")
    else :
        print(a + b)
N=int(input())

A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*400000
E=[0]*400000

ans=0

for i in range(N):
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  D[A[i]+i+1]+=1
  E[-A[i]+i+1]+=1

for i in range(len(D)):
  #ans+=C.count(i)
  ans+=D[i]*E[i]

print(ans)

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
#B=[]
#C=[]
D=[0]*1000000
E=[0]*1000000
 
ans=0
 
for i in range(N):
  if A[i]<500000:
  #B.append(A[i]+i+1)
  #C.append(-A[i]+i+1)
  #if -A[i]+i>=0:
  	D[A[i]+i]+=1
  	E[-A[i]+i]+=1
   #print(E[-A[i]+i],-A[i]+i)

for i in range(1000000):
  #ans+=C.count(i)
  ans+=D[i]*E[i]
 
print(ans)
n = int(input())
l = [list(map(int,input().split())) for i in range(n)]
v = n*(n-1)//2
E = [[] for i in range(v)]
dic = {}
c = 0
for i in range(n):
    for j in range(n-1):
        a,b = i,l[i][j]-1
        if a > b:
            a,b = b,a
        if (a,b) in dic:
            l[i][j] = dic[(a,b)]
        else:
            dic[(a,b)] = c
            l[i][j] = dic[(a,b)]
            c += 1
    for j in range(n-2):
        E[l[i][j]].append(l[i][j+1])

def dfs(i):
    if visit[i]:
        if dis[i] == -1:
            return -1
        else:
            return dis[i]
    visit[i] = True
    d = 1
    for nex in E[i]:
        res = dfs(nex)
        if res == -1:
            return -1
        d = max(d,res+1)

    dis[i] = d
    return d

visit = [False]*v
dis = [-1]*v
print(dfs(l[0][0]))


### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    ans = 1
    count = [0]*n
    check = set()
    game = []
    for i in range(n):
        if count[i] >= n-1 or i in check:
            continue
        ind = l[i][count[i]]-1
        if ind in check:
            continue
        if l[ind].index(i+1) == count[ind]:
            check |= set([i,ind])
            game.append([i,ind])
            count[i] += 1
            count[ind] += 1
    while True:
        gamepre = game
        check = set()
        game = []
        for i,j in gamepre:
            ci = True
            cj = True
            if count[i] >= n-1 or i in check:
                ci = False
            if count[j] >= n-1 or j in check:
                cj = False
            if ci:
                ci = True
                ind = l[i][count[i]]-1
                if ind in check:
                    ci = False
                if ci and l[ind].index(i+1) == count[ind]:
                    check |= set([i,ind])
                    game.append([i,ind])
                    count[i] += 1
                    count[ind] += 1
            if cj:
                cj = True
                ind = l[j][count[j]]-1
                if ind in check:
                    cj = False
                if cj and l[ind].index(j+1) == count[ind]:
                    check |= set([j,ind])
                    game.append([j,ind])
                    count[j] += 1
                    count[ind] += 1
        if not check:
            if sum(count) != n*(n-1):
                print(-1)
                exit()
            else:
                print(ans)
                exit()
        ans += 1
if __name__ == "__main__":
    main()
N, Q = map(int, input().split())		# 5 7
S = input()

#print(N,Q,S)

L = "0 " + S.replace('AC', '1 0 ').replace('T', '0 ').replace('G', '0 ')
R = "0 " + S.replace('AC', '0 1 ').replace('T', '0 ').replace('G', '0 ')

L = list( map(int, L.split()) )	# 1 2 3 4 5 ...
R = list( map(int, R.split()) )	# 1 2 3 4 5 ...

#L = [0,1,2,3,4,5,6,7,8,9]
#R = [0,1,2,3,4,5,6,7,8,9]
#print(N,Q,S,L,R)
#print(N,Q,S)
#print("L", L)
#print("R", R)


from functools import reduce
#print( reduce(lambda x,y: x+y, L) )	#=> 10 (=sum(1,2,3,4))


for q in range(1,Q+1):
	ans=0
	l, r = map(int, input().split())		# 5 7
	
	if l!=r:
		X=L[l:l+1]
		Y=R[l+2:r+1]
		Z=X+Y+[0]
		
		ans = reduce(lambda x,y: x+y, Z)	#=> 10 (=sum(1,2,3,4))

		#print(l,r,"X=",X,"Y=",Y,"Z=",Z,ans)

	print(ans)
	

### FIXED CODE ###

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

C=[0]*(N)
c=0
for i in range(len(S)-1):
  if S[i:i+2]=="AC": c += 1
  C[i] = c

#print(C)

for q in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1

  ans = C[r-1] - C[l-1]
  print(ans)
# -*- coding:utf-8 -*-
import sys

def main():
    data = []
    while(True):
        line = raw_input()
        if not line: break
        data.append(line)
    for answer in proc(data):
        print answer

def proc(data):
    return [passwd for passwd in data if is_hitofude(passwd)]

def is_hitofude(text):
    for first, second in get_pair(text):
        if second == '': break
        if not _can_slide(first, second):
            return False
    return True

def get_pair(text):
    pair_list = list(text)
    pair_list.reverse()
    while(True):
        if 2 <= len(pair_list):
            yield (pair_list.pop(), pair_list[-1])
        elif 1 == len(pair_list):
            yield (pair_list.pop(), '')
        else:
            break

matrix = ["ABC",
          "DEF",
          "GHI"]
pair = []
for y, row in enumerate(matrix):
    for x, base in enumerate(row):
        if x+1 < len(row): pair.append((base, row[x+1])) #EF
        if 0 <= x-1 : pair.append((base, row[x-1])) #ED
        if y+1 < 3: pair.append((base, matrix[y+1][x])) #EH
        if 0 <= y-1: pair.append((base, matrix[y-1][x])) #EB

def _can_slide(first, second):
    return (first, second) in pair

if __name__ == '__main__':
    main()

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys

def main():
    data = []
    for passwd in sys.stdin.readlines():
        data.append(passwd.strip())
    for answer in proc(data):
        print answer
    return 0

def proc(data):
    return [passwd for passwd in data if is_hitofude(passwd)]

def is_hitofude(text):
    for first, second in get_pair(text):
        if second == '': break
        if not _can_slide(first, second):
            return False
    return True

def get_pair(text):
    pair_list = list(text)
    pair_list.reverse()
    while(True):
        if 2 <= len(pair_list):
            yield (pair_list.pop(), pair_list[-1])
        elif 1 == len(pair_list):
            yield (pair_list.pop(), '')
        else:
            break

matrix = ["ABC",
          "DEF",
          "GHI"]
pair = []
for y, row in enumerate(matrix):
    for x, base in enumerate(row):
        if x+1 < len(row): pair.append((base, row[x+1])) #EF
        if 0 <= x-1 : pair.append((base, row[x-1])) #ED
        if y+1 < 3: pair.append((base, matrix[y+1][x])) #EH
        if 0 <= y-1: pair.append((base, matrix[y-1][x])) #EB

def _can_slide(first, second):
    return (first, second) in pair

if __name__ == '__main__':
    main()
N = int(input())
H = list(map(int, input().split()))
c = 0
for i in range(N-1):
  if H[i] > H[i+1]:
    H[i+1] = H[i+1] + 1
  if H[i] <= H[i+1]:
    C += 1
if C == N-1:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
c = 0
for i in range(N-1):
  if H[i] > H[i+1]:
    H[i+1] = H[i+1] + 1
  if H[i] <= H[i+1]:
    c += 1
if c == N-1:
  print('Yes')
else:
  print('No')
N = int(input())
v = list(map(int,input().split()))

sum = 0

for i in range(v)
	sum = 1/v[i] + sum

ans = 1/(sum/N)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
 
sum = 0
 
for i in range(len(A)):
	sum = (1/A[i]) + sum

a = 1/(sum)
 
print(a)
N = int(input())
A = list(map(int, input().split()))

c = 0
for i in range(1, N):
  if A[i-1] > A[i]:
  	c += A[i-1] - A[i]
    A[i] = A[i-1]
  
  
print(c)


### FIXED CODE ###

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

c = 0
for i in range(1, N):
  if A[i-1] > A[i]:
    c += A[i-1] - A[i]
    A[i] = A[i-1]
  
  
print(c)
def f(n):
      d = 2
      ans = 0
      while n>d:
        d*=5
        n//=d
        ans+=n
      return ans
     
    print(f(int(input())))

### FIXED CODE ###

def f(n):
  ans = 0
  while n>0:
    n//=5
    ans+=n
  return ans

x = int(input())
print(0 if x%2 else f(x//2))
H, W = map(int, input().split())

L = [0]
R = [0]
m = []
l = []
end = 0
for i in range(H):
    h = list(input())
    m.append(h)
    for j, w in enumerate(h):
        if w == '#':
            l.append([i, j])
            end += 1
HW = H * W
ans = 0
while (end < HW):
    nl = []
    for ll in l:
        if (0 < ll[0]):
            if (m[ll[0] - 1][ll[1]] == '.'):
                m[ll[0] - 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] - 1, ll[1]])

        if (ll[0] < W - 1):
            if (m[ll[0] + 1][ll[1]] == '.'):
                m[ll[0] + 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] + 1, ll[1]])

        if (0 < ll[1]):
            if (m[ll[0]][ll[1] - 1] == '.'):
                m[ll[0]][ll[1] - 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] - 1])

        if (ll[1] < H - 1):
            if (m[ll[0]][ll[1] + 1] == '.'):
                m[ll[0]][ll[1] + 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] + 1])
        l = nl
    ans += 1

print(ans)


### FIXED CODE ###



H, W = map(int, input().split())

m = []
l = []
end = 0
for y in range(H):
    h = list(input())
    m.append(h)
    for x, w in enumerate(h):
        if w == '#':
            l.append([y, x])
            end += 1
HW = H * W
ans = 0
# print(m[2][0]) m[y][x]
while (end < HW):
    nl = []
    for ll in l:
        if (0 < ll[1]):
            if (m[ll[0]][ll[1] - 1] == '.'):
                m[ll[0]][ll[1] - 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] - 1])

        if (ll[1] < W - 1):
            if (m[ll[0]][ll[1] + 1] == '.'):
                m[ll[0]][ll[1] + 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] + 1])

        if (0 < ll[0]):
            if (m[ll[0] - 1][ll[1]] == '.'):
                m[ll[0] - 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] - 1, ll[1]])

        if (ll[0] < H - 1):
            if (m[ll[0] + 1][ll[1]] == '.'):
                m[ll[0] + 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] + 1, ll[1]])

    l = nl
    ans += 1

print(ans)
a,b = (int(x) for x in input().split())
c = a * b
if c/2 % 0:
    print("Even")
else:
    print("Odd")



### FIXED CODE ###

a,b = (int(x) for x in input().split())
c = a * b
if c%2 !=0:
    print("Odd")
else:
    print("Even")
N = int(input())
A = list(map(int,input().split()))
B = [A[0],A[1],A[0]^A[1]]
flag = 0
for i in range(2,N):
    if A[i] not in C:
        flag = 1
        break
if flag==1:
    print("No")
else:
    if N%3==0:
        if A[0]==A[1]==0:
            print("Yes")
        elif A[0]==0 or A[1]==0:
            cnt = 0
            for i in range(N):
                if A[i]==0:
                    cnt += 1
            if cnt==N//3:
                print("Yes")
            else:
                print("No")
        else:
            C = {A[0]:0,A[1]:0,A[0]^A[1]:0}
            for i in range(N):
                C[A[i]] += 1
            if C[A[0]]==C[A[1]]==C[A[0]^A[1]]:
                print("Yes")
            else:
                print("No")
    else:
        if A[0]==A[1]==0:
            print("Yes")
        else:
            print("No")
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = set(A)
C = list(B)
k = len(C)
if N%3==0:
    if k==3 and C[0]^C[1]==C[2] and A.count(C[0])==A.count(C[1]) and A.count(C[0])==A.count(C[2]):
        print("Yes")
    elif k==2:
        C = sorted(C)
        if C[0]==0 and A.count(C[0])==N//3:
            print("Yes")
        else:
            print("No")
    elif k==1 and C[0] == 0:
        print("Yes")
    else:
        print("No")
else:
    if k==1 and C[0] ==0:
        print("Yes")
    else:
        print("No")
def main():
	n,m = map(int,input().split())
	# a = list(map(int,input().split()))
	# l = [str(input()) for i in range(n)]
	
	# m_pre = int(m)
	# ans = []
	# while n > 1:
	# 	print(n%m)
	# 	ans.append(n%m)
	# 	print("n = {}".format(n))
	# 	n = (n - (n%m)) // m
	# if n<m:
	# 	ans.append(1)
	# ans.reverse()
	# print(len(''.join(map(str,ans))))
	if n > m:
    	ans = 1
    else:
		ans = 0
	while n >= m:
		n = (n-n%m) // m
		ans += 1
	# if n < m:
	# 	ans -= 1
	print(ans)
	
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	n,m = map(int,input().split())
	ans = 1
	while n >= m:
		n = (n-n%m) // m
		ans += 1
	print(ans)

if __name__ == '__main__':
	main()
H, W = [int(_) for _ in input().split()]
S = []
for _ in range(H):
    S += [1 if _ == '.' else 0 for _ in list(input())]
S += [0] * W
SL = S.copy()
SR = S.copy()
SU = S.copy()
SD = S.copy()
for h in range(H):
    for i in range(W * h + 1, W * (h + 1)):
        if SL[i]:
            SL[i] = SL[i - 1] + 1
        else:
            SL[i] = 0
for h in range(H):
    for i in range(W * h - 2, W * (h - 1) - 1, -1):
        if SR[i]:
            SR[i] = SR[i + 1] + 1
        else:
            SR[i] = 0
for w in range(W):
    for i in range(W + w, W * H + w, W):
        if SU[i]:
            SU[i] = SU[i - W] + 1
        else:
            SU[i] = 0
for w in range(W):
    for i in range(W * (H - 2) + w - 1, -1, -W):
        if SD[i]:
            SD[i] = SD[i + W] + 1
        else:
            SD[i] = 0
score = 0
print(max((SL[_] + SR[_] + SU[_] + SD[_] - 3 for _ in range(H * W))))


### FIXED CODE ###

import copy
H, W = [int(_) for _ in input().split()]
S = []
for _ in range(H):
    S += [1 if _ == '.' else 0 for _ in list(input())]
S += [0] * W
SL = copy.copy(S)
SR = copy.copy(S)
SU = copy.copy(S)
SD = copy.copy(S)
for h in range(H):
    for i in range(W * h + 1, W * (h + 1)):
        if SL[i]:
            SL[i] = SL[i - 1] + 1
        else:
            SL[i] = 0
for h in range(H):
    for i in range(W * h - 2, W * (h - 1) - 1, -1):
        if SR[i]:
            SR[i] = SR[i + 1] + 1
        else:
            SR[i] = 0
for w in range(W):
    for i in range(W + w, W * H + w, W):
        if SU[i]:
            SU[i] = SU[i - W] + 1
        else:
            SU[i] = 0
for w in range(W):
    for i in range(W * (H - 2) + w - 1, -1, -W):
        if SD[i]:
            SD[i] = SD[i + W] + 1
        else:
            SD[i] = 0
score = 0
print(max((SL[_] + SR[_] + SU[_] + SD[_] - 3 for _ in range(H * W))))
import sys

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

for i in range(1, N):
    if H[i] >= H[i-1] - 1:
        H[i-1] -= 1
    elif H[i] < H[i-1] - 1:
        print("No")
        sys.exit()

if flag == 0:
    print("Yes")

### FIXED CODE ###

import sys

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

for i in range(1, N):
    if H[i] + 1 == H[i-1]:
        H[i] += 1
    elif H[i] + 1 < H[i-1]:
        print("No")
        sys.exit()
    
print("Yes")
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num)
    
    return cnt


while True:
    mid = (left + right) // 2
    tmp = count(mid)
    if tmp == K:
        break
    elif tmp > K:
        if left == mid:
            mid += 1
            break
        left = mid
    else:
        right = mid

if mid == 0:
    print(mid)
    exit()
print(mid)
'''
right = mid
while True:
    tmp = count(mid)
    if tmp == K and tmp != count(mid-1):
        print(mid)
        break
    elif tmp == K:
        right = mid
    else:
        if left == mid:
            print(mid+1)
            break
        left = mid
    mid = (left + right) // 2
'''

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt

while True:
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        exit()
    tmp = count(mid)
    if right - left <= 1:
        mid = right
        break
    elif tmp > K:
        left = mid
    else:
        right = mid

right = mid

while True:
    tmp = count(mid)
    if right - left <= 1:
        print(right)
        break
    elif tmp == K:
        right = mid
    else:
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, a: "List[int]"):
    from collections import Counter
    ma, mi = max(a), min(a)
    if ma >= N or mi < 1:
        raise
    if ma - mi > 1:
        return False
    if ma == mi:
        return ma == N - 1 or  2 * ma <= N
    c = Counter(a)
    if c[ma] % 2 != 0:
        return False
    return ma != c[ma] // 2 + c[mi] - 1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(YES if solve(N, a) else NO)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, a: "List[int]"):
    from collections import Counter
    ma, mi = max(a), min(a)
    if ma >= N or mi < 1:
        raise
    if ma - mi > 1:
        return False
    if ma == mi:
        return ma == N - 1 or  2 * ma <= N
    c = Counter(a)
    # pairがpairでない
    if c[ma] % 2 != 0:
        return False
    x = ma - c[ma] // 2
    if x < 0:
        return False
    # pair以外、すべてalone(crowdが0個)
    if x == c[mi]:
        return True
    # crowdを1つ以上作れるなら0以上c[mi]-2以下の好きな數を作れる
    return x <= c[mi] - 2

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(YES if solve(N, a) else NO)

if __name__ == '__main__':
    main()