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

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

for k in range(K):
    B = [0] * N
    for i in range(N):
        d = A[i]
        for j in range(-d, d+1):
            index = i + j
            if 0 <= index < N:
                B[index] += 1
    A = B
print(" ".join(map(str, A)))


### FIXED CODE ###

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

for k in range(K):
    for i in range(N):
        if A[i] != N:
            break
    else:
        break

    B = [0] * N
    for i in range(N):
        d = A[i]
        left = max(0, i - d)
        right = min(N-1, i + d)
        B[left] += 1
        if right + 1 < N:
            B[right+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B
print(" ".join(map(str, A)))
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
memo = {}

exp = []
for p in P:
  if p in memo:
    exp.append(memo[p])
  else:
    cnt = p-1+1
    r = 0
    for i in range(1, p+1):
      r += i*(cnt**-1)
    exp.append(r)
    memo[p] = r

res = 0
i = 0
k = K
while k <= N:
  res = max(res, sum(exp[i:k]))
  i += 1
  k += 1

print(res)

### FIXED CODE ###

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

T = [0] * (N+1)

for i in range(N):
  T[i+1] = T[i] + (1+p[i])/2

ans = 0
for j in range(K, N+1):
  ans = max(ans, T[j]-T[j-K])

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

def main():
    N, K = map(int,input().split())
    moves = []
     
    mod = 998244353
     
    for _ in range(K):
        L, R = map(int,input().split())
        # for d in range(L, R+1):
        #     moves.append(d)
        moves.append((L, R))
    # moves.sort()
     
    dp = [0] * (N + 1)
    dp[1] = 1
    # for dis in moves:
    #     dp[dis] = 1
    # print(moves)
     
    for n in range(1, N+1):
        for L, R in moves:
            if n - L <= 0 :
                continue
            for dis in range(L, R+1):
                if n - dis >= 1:
                    dp[n] += dp[n - dis] % mod
                else:
                    break
     
    # print(dp)
    print(dp[N] % mod)

if __name__ == "__main__":
    main()


### FIXED CODE ###

n, k = map(int, input().split())
sec = [list(map(int, input().split())) for _ in range(k)]
sec.sort()
    
mod = 998244353
    
dp = [0] * n
dp[0] = 1
sum_dp = [0, 1]
for i in range(1, n):
    for l, r in sec:
        if i - l < 0:
            break
        elif i - r > 0:
            dp[i] = ((dp[i] + sum_dp[i-l+1]) % mod - sum_dp[i-r]) % mod
        else:
            dp[i] = (dp[i] + sum_dp[i-l+1]) % mod
    
    sum_dp.append((sum_dp[-1] + dp[i]) % mod)
    
print(dp[n-1])
### BUGGY CODE ###

import numpy as np
a=int(input())
c=[0]*a
d=[0]*10
x=0
for i in range(a):
	e=input()
	for j in range(10):
		d[j]=e[j]
	d.sort()
	c[i]=d[0]+d[1]+d[2]+d[3]+d[4]+d[5]+d[6]+d[7]+d[8]+d[9]

for k in range(0,a):
	for l in range(k+1,a):
		if c[k]==c[l]:
			x=x+1
print(x)

### FIXED CODE ###

import numpy as np
from collections import Counter
a=int(input())
c=[0]*a
d=[0]*10
x=0
y=a
z=0
for i in range(a):
	e=input()
	for j in range(10):
		d[j]=e[j]
	d.sort()
	c[i]=d[0]+d[1]+d[2]+d[3]+d[4]+d[5]+d[6]+d[7]+d[8]+d[9]

mycounter = Counter(c)
lst=[]
for e in mycounter.items():
    lst.extend(e)
for t in range(1,len(lst),2):
	k=lst[t]
	z=int(z+(k*(k-1)/2))
print(z)
### BUGGY CODE ###

s = input()
divisor = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(len(s) + 1)]
dp[0][0] = 1
for i in range(len(s)):
  if s[i] == '?':
    for j in range(10):
      for k in range(13):
        dp[i + 1][(k * 10 + j) % 13] += dp[i][k]
  else:
    t = int(s[i])
    for k in range(13):
      dp[i + 1][(k * 10 + t) % 13] += dp[i][k]
  for k in range(13):
    dp[i + 1][k] %= divisor
print(dp[len(s)][5])


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

import sys
n = int(input())
D = {}
sys.stdout.flush()
print(0)
s = input()
if s == "Vacant":
    sys.exit()
D[0] = s
inf = 0
sys.stdout.flush()
print(n-1)
s = input()
if s == "Vacant":
    sys.exit()
sup = n-1
D[n-1] = s
while 1:
    mid = (sup+inf)//2
    sys.stdout.flush()
    print(mid)
    s = input()
    if s == "Vacant":
        break
    else:
        D[mid] = s
        if D[inf] != D[mid]:
            sup = mid-1
        else:
            inf = mid+1

### FIXED CODE ###

import sys
n = int(input())
D = {}
for i in [0,n-1]:
    print(i,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    D[i] = s
inf = 0
sup = n
while True:
    mid = (sup+inf)//2
    print(mid,flush=True)
    s = input()
    if s == "Vacant":
        sys.exit()
    else:
        D[mid] = s
        if ((mid%2==inf%2) != (D[mid] == D[inf])):
            sup = mid
        else:
            inf = mid
### BUGGY CODE ###

def K(n):
    return 0.5 * (n + 1)

def d():
    n, k = input().split()
    n = int(n)
    k = int(k)
    p = input().split()

    m = 0
    for i in range(0, len(p)-k+1):
        a = 0
        for i2 in range(k):
            a += int(p[i+i2])
        if m < a:
            m = a
            I = i
    m2 = 0
    for i in range(k):
        m2 += K(int(p[I + i]))
    return m2
print(d())

### FIXED CODE ###

def K(n):
    return 0.5 * (n + 1)

def d():
    n, k = list(map(int, input().split()))
    p = list(map(int, input().split()))

    pionta = None
    ire = [None for i in range(k)]
    d = {}
    d[0] = 0

    ss = 0
    for i in range(0, n):
        if k < i + 1:
            pionta = i % k
        if pionta is None:
            ire[i] = p[i]
        else:
            ss += p[i] - ire[pionta]
            d[ss] = i
            ire[pionta] = p[i]


    max_s = max(d.keys())
    i = d[max_s]
    m = 0
    for i2 in range(i-k+1, i+1):
        m += K(p[i2])
    return m
print(d())
### BUGGY CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
n=int(input())
s=input().rstrip('\n')

from collections import Counter
a=Counter(s)
#print(a)
num=a["R"]*a["G"]*a["B"]
#print(num)
for i in range(n-2):
    for j in range(1,n):
        if i+2*j<n:
            #print([i,i+j,i+2*j,s[i], s[i+j], s[i+2*j]])
            if set([s[i],s[i+j],s[i+2*j]])==set(["R","G","B"]):
                num-=1
print(num)


### FIXED CODE ###


def main():
    import sys
    input = sys.stdin.readline
    #n = int(input())
    #l = list(map(int, input().split()))
    '''
    A=[]
    B=[]
    for i in range():
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)'''

    n=int(input())
    s=input().rstrip('\n')
    a=0
    b=0
    c=0
    for i in range(n):
        if s[i]=="R":
            a+=1
        elif s[i]=="G":
            b+=1
        elif s[i]=="B":
            c+=1
    num=a*b*c
    #print(num)
    for i in range(n-2):
        for j in range(1,n//2+1):
            if i+2*j<n:
                if s[i]!=s[i+j] and s[i+j]!=s[i+2*j] and s[i]!=s[i+2*j]:
                    num-=1
    print(num)

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

#!python3

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]

    AB.sort(key=lambda a: (a[0]/a[1], a[0]), reverse=True)

    S = []
    for a, b in AB:
        h = H
        i = 1
        while h >= i:
            S.append((a*i, b*i))
            h -= i
            i <<= 1
        if h:
            S.append((a*h, b*h))

    N2 = len(S)
    def ubound(b, a, i):
        for j in range(i, N2):
            aj, bj = S[j]
            if a + aj >= H:
                return (b+bj, b + (H-a) * bj / aj)
            a += aj
            b += bj

        return (inf, inf)

    q = []
    u0, u1 = ubound(0, 0, 0)

    inf = float("inf")
    heappush(q, (u1, u0, 0, 0, 0))
    um = u0
    #print(AB)
    #print(H, S)
    while q:
        #print(q)
        uq0, uq1, aq, bq, i = heappop(q)

        if uq0 >= um:
            break

        if i >= N2: continue

        ai, bi = S[i]
        if aq + ai < H:
            heappush(q, (uq0, uq1, aq + ai, bq + bi, i + 1))

        u0, u1 = ubound(bq, aq, i + 1)
        if u1 <= um:
            if u0 < um:
                um = u0
            heappush(q, (u1, u0, aq, bq, i + 1))

    print(um)



if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!python3
import sys
sys.setrecursionlimit(1000000)

from heapq import heappush, heappop, heapify

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, N = iim()
    AB = [tuple(iim()) for i in range(N)]
    inf = float("inf")
    AB.sort(key=lambda a: (a[0]/a[1], -a[0]), reverse=True)

    def memo(f):
        cache = {}
        def wrapper(*a):
            if a in cache:
                return cache[a]
            b = f(*a)
            cache[a] = b

            return b

        return wrapper

    @memo
    def calc(h):
        if h <= 0: return 0

        bi = inf
        for a, b in AB:
            bj = b + calc(h - a)
            if bi > bj:
                bi = bj
            else:
                break
        return bi

    print(calc(H))



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

K = int(input())
def pgcd(x,y):
  while y>0:
    x,y=y,x%y
  return x
s = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      s+=pgcd(pgcd(a,b),c)
print(s)

### FIXED CODE ###

from math import*
K=int(input())
N=0
k=K*K
d1=[0]*int(k)
i=0
j=0
for b in range(K):
    for c in range(K):
        d1[i]=gcd((c+1),(b+1))
        i+=1
for a in range(K):
    for x in d1:
        N+=gcd(x,(a+1))
print(N)
### BUGGY CODE ###

import itertools
from operator import mul
from functools import reduce
def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
N = int(input())
S = [int(s) for s in input()]
num = {s:[] for s in S}
for i, s in enumerate(S):
    num[s].append(i)
ans = combinations_count(N, 3)
check = []
for i in list(num.keys()):
    for j in list(num.keys()):
        for k in list(num.keys()):
            s = str(i) + str(j) + str(k)
            if s not in check and (len(num[i]) > 1 or len(num[j]) > 1 or len(num[k]) > 1):
                temp = 0
                check.append(s)
                for a in num[i]:
                    for b in num[j]:
                        for c in num[k]:
                            if a < b < c:
                                temp += 1
                #print(i, j, k, temp)
                if temp > 0:
                    ans -= (temp-1)
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0
for i in range(1000):
    v = str(i).zfill(3)
    idx = 0
    c = 0
    idx_now = 0
    for j in range(3):
        idx = S[idx_now:].find(v[j])
        if idx == -1:
            break
        else:
            idx_now += idx + 1
            c += 1
    if c == 3:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict,deque

def main():
    N = int(input())
    dist = [[] for i in range(N)]
    c = [[] for _ in range(N)]
    l = 0
    d = defaultdict(tuple)
    for i in range(N-1):
        a,b = map(int,input().split())
        dist[a-1].append(b-1)
        l = max(l,len(dist[a-1]))
        d[(a-1,b-1)] = i

    q = deque([0])
    ans = [0 for _ in range(N-1)]
    while q:
        now = q.popleft()
        col = 1
        for fol in dist[now]:
            for i in range(col,N+1):
                if i not in c[now]:
                    ans[d[(now,fol)]] = i
                    c[now].append(i)
                    c[fol].append(i)
                    col += 1
                    break
            q.append(fol)
            
    print(max(ans))
    for i in ans:
        print(i)
        
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

def main():
    N = int(input())
    e = []
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a,b = map(int,input().split())
        e.append(b)
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    col = 0
    for x in edge:
        col = max(col,len(x))
        
    print(col)
    ans = [-1 for _ in range(N)]
    go = [False for _ in range(N)]
    q = deque([0])
    while q:
        now = q.pop()
        go[now] = True
        c = 0
        for fol in edge[now]:
            if go[fol]:
                continue
            if c != ans[now]:
                ans[fol] = c
            else:
                ans[fol] = col-1
            c += 1
            q.append(fol)
    
    for i in range(N-1):
        print(ans[e[i]-1]+1)

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

from collections import defaultdict as dd
import queue
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(str(b))
    dic[str(b)].append(str(a))
seen = set()
def BFS(dic,node):
    cc = set()
    q = queue.Queue()
    q.put(node)
    cc.add(node)
    while not q.empty():
        now_node = q.get()
        cc.add(now_node)
        target = set(dic[now_node]) - cc
        for tgt in target:
            q.put(tgt)
    return cc
c_comp=[]
"""
for i in range(1,N+1):
    if str(i) not in seen:
        # 連結判定
        tmp = BFS(dic,str(i))
        seen = seen & set(tmp)
        c_comp.append(list(tmp))
"""
tg = set(range(1,N+1))
while len(tg)!=0:
    i = tg.pop()
    tmp = BFS(dic,str(i))
    seen = seen & set(tmp)
    c_comp.append(list(tmp))
    tg = tg - set(tmp)

uf = [0]*N
for i,ls in enumerate(c_comp):
    for val in ls:
        uf[int(val)-1] = i
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(str(b))
        dic[str(b)].append(str(a))
res = [0]*N
for ls in c_comp:
    leng = len(ls)-1
    for idx in ls:
        res[int(idx)-1] = leng - len(dic[idx])
print(*res)


### FIXED CODE ###

from collections import defaultdict as dd
import queue
import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(M)]
cd = [tuple(map(int,input().split())) for _ in range(K)]
dic = dd(list)
for (a,b) in ab:
    dic[str(a)].append(b)
    dic[str(b)].append(a)
uf = [-1]*N
def BFS(ufid, dic, node):
    leng = -1
    q = queue.Queue()
    q.put(node)
    while not q.empty():
        now_node = q.get()
        if uf[now_node-1] > 0:
            continue
        leng += 1
        uf[now_node-1] = ufid
        target = [val for val in dic[str(now_node)] if uf[val-1]==-1]
        for tgt in target:
            q.put(tgt)
            uf[tgt-1] = 0
    return leng

len_ls = []
var = 1
for i in range(N):
    if uf[i] == -1:
        # 連結判定
        leng = BFS(var, dic, i+1)
        len_ls.append(leng)
        var += 1
for (a,b) in cd:
    if uf[a-1] == uf[b-1]:
        dic[str(a)].append(b)
        dic[str(b)].append(a)
res = [len_ls[uf[i]-1] - len(dic[str(i+1)]) for i in range(N)]
print(*res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = []
for _ in range(N):
    s,t,x = rl()
    TT.append([s-x-0.5,1,x])
    TT.append([t-x-0.5,-1,x])
for i in range(Q):
    d = ri()
    TT.append([d,0,i])


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.append(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')

### FIXED CODE ###

import sys
input = sys.stdin.readline
ri = lambda: int(input())
rl = lambda: [int(x) if x.isdecimal() else x for x in input().split()]
#rl = lambda: list(input().split()))
rr = lambda N: [list(l) for l in zip(*[rl() for _ in range(N)])]
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')
OE = lambda x: print('Odd') if x%2 else print('Even')
INF = 10**18
MOD = 10**9+7


N,Q=rl()
TT = []
now = set()
for _ in range(N):
    s,t,x = rl()
    TT.append((s-x-0.5,1,x))
    TT.append((t-x-0.5,-1,x))
for i in range(Q):
    d = ri()
    TT.append((d,0,i))


TT.sort()
mx = INF
mx_f = False
ans = [-1]*Q
for st,w,x in TT:
    if w > 0:
        now.add(x)
        if mx > x:
            mx = x
            mx_f = True
    elif w < 0:
        now.remove(x)
        if mx == x:
            mx_f = False
    elif len(now) > 0:
        if not mx_f:
            mx = min(now)
            mx_f = True
        ans[x] = mx
print(*ans,sep='\n')
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [[[0 for _ in range(4)] for i in range(m)] for j in range(n)]
q = deque()
q.append([0,0])
dp[0][0][1] = value[0][0]
while q:
    oy,ox = q.popleft()
    for dy,dx in [(1,0),(0,1)]:
        ny = oy + dy
        nx = ox + dx
        if 0 <= ny < n and 0 <= nx < m:
            nva = value[ny][nx]
            if dx: #　横移動
                for k in range(4):
                    dp[ny][nx][k] = dp[oy][ox][k]
                    if k and nva:
                        dp[ny][nx][k] = max(dp[ny][nx][k], dp[oy][ox][k-1] + nva)
            else: #縦
                dp[ny][nx][0] = max(dp[oy][ox])
                if nva:
                    dp[ny][nx][1] = dp[ny][nx][0] + nva
            q.append([ny,nx])
# pprint.pprint(dp)
print(max(dp[-1][-1]))

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,k = inpl()
value = [[0 for _ in range(m)] for i in range(n)]
for _ in range(k):
    a,b,c = inpl()
    value[a-1][b-1] = c
dp = [0] * (4*(m+1)*(n+1))
def ind(i,j,k): 
    return 4*(m+1)*i + 4*j + k
for i in range(n):
    for j in range(m):
        for k in range(3)[::-1]:
            dp[ind(i,j,k+1)] = max(dp[ind(i,j,k+1)], dp[ind(i,j,k)] + value[i][j])
        for k in range(4):
            dp[ind(i+1,j,0)] = max(dp[ind(i+1,j,0)], dp[ind(i,j,k)])
            dp[ind(i,j+1,k)] = max(dp[ind(i,j+1,k)], dp[ind(i,j,k)])
# print(dp)
mx = 0
for k in range(4):
    mx = max(mx, dp[ind(n-1,m-1,k)])
print(mx)
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in A:
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    A.sort()
    B = [True]*(10**6+1)

    from collections import Counter
    c = Counter(A)
    bl = set()
    for k, v in c.items():
        if v >= 2:
            bl.add(k)

    ans = 0
    for a in set(A):
        if a not in bl and B[a]:
            ans += 1
        for i in range(1, 10**6):
            if 10**6 < a*i:
                break
            B[a*i] = False
    print(ans)


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

import collections

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

c = collections.Counter(x)
li = []
for i in c.values():
    li.append(i)

li.sort(reverse=True)

while li[0] != 1:
    for i in range(len(li)-1):
        if li[i] >= 3 and li[i] % 2 == 0:
            li[i] = 2
        elif li[i] >= 3 and li[i] % 2 != 0:
            li[i] = 1

        if li[i+1] == 2 and li[i] == 2:
            li[i+1] = 1
            li[i] = 1
    li.sort(reverse=True)
    if len(li) > 1 and li[0] == 2 and li[1] == 1:
        li[0] -= 1
        li.pop(-1)

print(len(li))




### FIXED CODE ###

import collections

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

c = collections.Counter(x)
li = []
for i in c.values():
    li.append(i)

li.sort(reverse=True)

for j in range(2):
    for i in range(len(li) - 1):
        if li[i] >= 3 and li[i] % 2 == 0:
            li[i] = 2
        elif li[i] >= 3 and li[i] % 2 != 0:
            li[i] = 1

        if li[i + 1] == 2 and li[i] == 2:
            li[i + 1] = 1
            li[i] = 1
    li.sort(reverse=True)
    if len(li) > 1 and li[0] == 2 and li[1] == 1:
        li[0] -= 1
        li.pop(-1)


print(len(li))
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
cost=[0,2,5,5,4,5,6,3,7,6]
dp=[-2*n]*(n+10)
dp[0]=0
ans=[]
for i in range(1,n+1):
    for j in cost:
        if i>=j:
            dp[i]=max(dp[i],dp[i-j]+1)
cnt=n
while cnt:
    for j in a:
        if cnt>=j and dp[cnt-cost[j]]==dp[cnt]-1:
            ans.append(j)
            cnt-=cost[j]
            break
for j in ans:
    print(j, end="")
print("")

### FIXED CODE ###

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

A.sort()
A.reverse()

match = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [-N-N] * (N + 1)
dp[0] = 0

for i in range(1, N + 1):
  for j in A:
    if i >= match[j]:
      dp[i] = max(dp[i], dp[i - match[j]] + 1)

max_list = []
while N:
  for j in A:
    if N >= match[j] and dp[N] == dp[N - match[j]] + 1:
      max_list.append(j)
      N -= match[j]
      break

for j in max_list:
  print(j, end="")
print("")
### BUGGY CODE ###

import bisect

n = int(input())
L = list(map(int, input().split()))
ans = 0
c = 0

L.sort()

for i in range(n-2):
    for j in range(i+1, n):
        c = L[i]+L[j]
        l = j
        r = bisect.bisect_left(L, c, lo=l) -1
        ans += (r-l)

print(ans)

### FIXED CODE ###

import bisect

n=int(input())
L=sorted(list(map(int,input().split())))

ans=0
for i in range(n-1):
  for j in range(i+1,n):
    idx=bisect.bisect_left(L,L[j]+L[i])
    ans+=max(0,idx-j-1)

print(ans)