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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    from collections import deque
    from collections import Counter
    dq = deque(a)
    ans = []
    cnt = Counter(a)
    for i in range(n):
        if len(dq) == 0:
            break

        tmp = dq.popleft()

        for j in range(len(dq)):
            tmp2 = dq.popleft()
            if tmp2 % tmp == 0:
                continue
            dq.append(tmp2)
        if cnt[tmp] > 1:
            continue
        ans.append(tmp)

    print(len(ans))

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

s = input()
k = int(input())
substrings = []
for i in range(len(s)):
    for j in range(len(s)-i):
        if s[i:i+j+1] not in substrings: substrings.append(s[i:i+j+1])

substrings.sort()
print(substrings[k-1])

### FIXED CODE ###

s = input()
k = int(input())
substrings = []

for i in range(len(s)):
    for j in range(i, min(len(s), i+5)):
        if s[i:j+1] not in substrings: substrings.append(s[i:j+1])

substrings.sort()
print(substrings[k-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
from itertools import combinations
AA = list(combinations(A,2))
ans = 0
for a,b in AA:
    ans += a^b
print(ans%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
ans = 0

for bit in range(60):
    m = 1 << bit
    # bit桁目のbitが立っている時の数
    c = sum(a&m for a in A) >> bit
    # bit桁目の1の合計
    ans += (c*(N-c))<<bit
    # 繰り上がりのない足し算
    ans %= mod
print(ans)
### BUGGY CODE ###

#input
N, M = map(int, input().split())
A = [0] * N
B = [0] * N

for i in range(N):
    A[i], B[i] = map(int, input().split())

#output
import heapq

#点数配列の用意
point = 0
hq = []
#M-i日目(1 <= i <= M)に働ける仕事の中で、Bが最大のものを選ぶ
for j in range(0, M):
    for i in range(N):
        if A[i] == j + 1:
            heapq.heappush(hq, -B[i])
    if len(hq):
        point += -heapq.heappop(hq)
print(point)

### FIXED CODE ###

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

jobs = {}
for _ in range(N):
    A, B = map(int, input().split())
    if A > M :
        continue
    if A in jobs:
        jobs[A].append(B)
    else:
        jobs[A] = [B]

#output
import heapq

#点数配列の用意
point = 0
hq = []
#M-i日目(1 <= i <= M)に働ける仕事の中で、Bが最大のものを選ぶ
for A in range(1, M+1):
    if A in jobs:
        for B in jobs[A]:
            heapq.heappush(hq, -B)
    else:
        if len(hq) == 0:
            continue
    point += -heapq.heappop(hq)

print(point)
### BUGGY CODE ###

a,b=map(int, input().split())
c=list(map(int, input().split()))
l =[]
ans = 0

for i in range(a-b+1):
    for k in range(b):
        ans += (c[i+k]+1)/2
    l.append(ans)
    ans = 0

L = sorted(l)
print(L[-1])

### FIXED CODE ###

a,b=map(int, input().split())
c=list(map(int, input().split()))
l =[]
ans = 0

def abc(n):
    return (n+1)/2

cb = list(map(abc,c))

s = sum(cb[:b])
l.append(s)

for i in range(b,a):
    s = s - cb[i-b] + cb[i]
    l.append(s)

L = sorted(l)
print(L[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N = int(input())

ans = 0
for i in range(1, N):
    ans += i

print(ans)

### FIXED CODE ###

N = int(input())

ans = (N * (N-1) // 2)
print(ans)
### BUGGY CODE ###

from collections import deque

d = deque(input())

q = int(input())

headflag = 0

for i in range(q):
    s = input()
    if len(s) == 1:
        if headflag == 0:
            headflag = 1
        else:
            headflag = 0
    else:
        l = list(s)
        if headflag == 0:
            if l[2] == '1':
                d.appendleft(l[4])
            else:
                d.append(l[4])
        else:
            if l[2] == '2':
                d.appendleft(l[4])
            else:
                d.append(l[4])

dl = len(d)

if headflag == 0:
    for i in range(len(d)):
        print(d[i], end='')
else:
    for i in range(len(d)):
        print(d[dl-1-i], end='')

print()


### FIXED CODE ###

from collections import deque

d = deque(input())

q = int(input())

headflag = 0

for i in range(q):
    s = input()
    if len(s) == 1:
        if headflag == 0:
            headflag = 1
        else:
            headflag = 0
    else:
        l = list(s)
        if headflag == 0:
            if l[2] == '1':
                d.appendleft(l[4])
            else:
                d.append(l[4])
        else:
            if l[2] == '2':
                d.appendleft(l[4])
            else:
                d.append(l[4])

result = ''.join(d)

if headflag == 0:
    print(result)
else:
    result = result[::-1]
    print(result)

print()
### BUGGY CODE ###

n= int(input())
s=[]
ans=0
for i in range(n):
    x=str(input()) 
    if x not in s:
        s.append(x)
        ans +=1
print(ans)

### FIXED CODE ###

n=int(input())
ans=0
s=[]
for i in range(n):
    s.append(str(input()))
s=set(s)
print(len(s))
### BUGGY CODE ###

N,K,Q=list(map(int,input().split()))
A=[int(input()) for _ in range (Q)]
B={i:0 for i in range(N)}
for i in range(Q):
    B[A[i]-1]+=1
for i in range(N):
    if 0>=K-sum(B.values())+B[i]:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

N,K,Q=list(map(int,input().split()))
A=[int(input()) for _ in range (Q)]
B=[0 for _ in range (N)]
for i in range(Q):
    B[A[i]-1]+=1
C=sum(B)-K
for i in range(N):
    if C>=B[i]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math

def gcd(a, b):
    while b: a, b = b, a % b
    return a


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2, 7, 61] if n < 1 << 32 else [2, 3, 5, 7, 11, 13, 17] if n < 1 << 48 else [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                                                                                     31, 37]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = y * y % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += i % 2 + (3 if i % 3 == 1 else 1)
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret


def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
    return [prime for prime in primes if prime != 0]


N = int(input())
DP = [0] * (N+1)
ans = 1
DP[1] = 1
for a in primes(N):
    cnt = 1
    while True:
        p = (a ** cnt) * (1 + cnt)
        DP[a ** cnt] = p
        ans += p
        cnt += 1
        if a ** cnt > N:
            break

for i in range(2, N+1):
    if DP[i] != 0:
        continue
    A = primeFactor(i)
    a = 1
    for key, value in A.items():
        a *= DP[key**value]
    DP[i] = a
    ans += a


print(ans)


### FIXED CODE ###

N = int(input())

Ans = [2 * i for i in range(N+1)]
Ans[0] = 0
Ans[1] = 1
ans = N * (N + 1) - 1
for i in range(2, N+1):
    if i * 2 > N+1:
        break
    for j in range(2 * i, N+1, i):
        Ans[j] += j
        ans += j

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

import numpy as np

MOD = 1000000007;

s = input()

n=len(s)

if n<1 or n>10**5:
	print ('Illegal')
	exit()

#a=[-1]*len(s)
b=np.zeros((n+1, 13), dtype = 'int64')
p=np.zeros(n,dtype=int)
#b=[[0 for i in range(13)] for j in range(n+1)]
#p=[0]*n


x=1
for i in reversed(range(n)):
	p[i]=x%13
	x=p[i]*10
	
for i in range(n):
	if(s[i]=="?"):
		c=-1
	else:
		c=int(s[i])
	if ( i== 0):
		if (c==-1):
			for j in range(10):
				b[0][(p[i]*j)%13]=1
		else:
			b[0][(p[i]*c)%13]=1
	else:
		if (c==-1):
			for j in range(10):
				for k in range(13):
					b[i][(k+p[i]*j)%13]+=b[i-1][k]
		else:
			for k in range(13):
				b[i][(k+p[i]*c)%13]+=b[i-1][k]

	for k in range(13):b[i][k]%=MOD
#	print (b[i])
#	print (b[i+1])

print (b[n-1][5])


### FIXED CODE ###

MOD = 1000000007;

s = [int(x) if x!="?" else -1 for x in input()]

n=len(s)

r=[0]*13

c=s[0]
if (c!=-1):
	r[c]=1
else:
	for i in range(10):r[i]=1

for i in range(1,n):
	dp=[0]*26
	for j in range(13):dp[j*10%13]+=(r[j]%MOD)
	dp[13:26]=dp[0:13]
	c=s[i]
	r=[0]*13
	if (c==-1):
		w=sum(dp[4:14])
		for j in range(13):
				r[j]+=w
				w=w+dp[j+1]-dp[4+j]
	else:
		for j in range(13):
			r[j]+=dp[13-c+j]
print (r[5]%MOD)
### BUGGY CODE ###

n=int(input())
*a,=map(int,input().split())
b=0
for i in range(n):
    b+=(sum(a)-sum(a[:i+1]))*a[i]
print(b%(10**9+7))

### FIXED CODE ###

n=int(input())
*a,=map(int,input().split())
s=sum(a)%(10**9+7)
c=0
b=0
for i in range(n):
    b+=a[i]
    amod=a[i]%(10**9+7)
    c+=(s-b)*amod
print(c%(10**9+7))
### BUGGY CODE ###

N = int(input())
S = str(input())

a = []
for i in range(10):
    for j in range(10):
        for z in range(10):
            a.append([i,j,z])

s = list(S)
ans = 0
for n in a:
    for i,name in enumerate(s):
        if int(name) == n[0]:
            n = n[1:]
        if len(n) == 0:
            ans += 1
            break

print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())

a = []
for i in range(10):
    for j in range(10):
        for z in range(10):
            a.append([i,j,z])

s = list(S)
s = [int(i) for i in s]
ans = 0
for n in a:
    flag = 0
    for i,name in enumerate(s):
        if name == n[0]:
            n = n[1:]
            flag += 1
        if flag == 3:
            ans += 1
            break

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

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

def lcm(x, y):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return (x * y) // gcd(x, y)
X = lcm(N ,M)

if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        counter = L
        y = L // N
        z = L // M
        match = lcm( y, z)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                counter = -1
                break
        if counter == L:
            break
    print(counter)




### FIXED CODE ###

N, M = map(int, input().split())
S = str(input())
T = str(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
def lcm(x, y):
    return (x * y) // gcd(x, y)
X = lcm(N ,M)
 
if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
        L = X
        match = lcm(  L // N,  L // M)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[ j * M * match // L]:
                L = -1
                break
        if L == X :
            print(L)
        else:
            print(-1)
### BUGGY CODE ###

import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        alphabet[ord(s)-ord("a")].pop(bisect.bisect_left(alphabet[ord(s)-ord("a")],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord('a')],A-1)
        #alphabet[ord(B)-ord('a')]=alphabet[ord(B)-ord('a')][:index]+[A-1]+alphabet[ord(B)-ord('a')][index:]
        #bisect.insort(alphabet[ord(B)-ord('a')],A-1)
        alphabet[ord(B)-ord('a')].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
s = list(input())
q = int(input())
query = [input() for _ in range(q)]

p = [[] for _ in range(26)]

for i, x in enumerate(s):
    p[ord(x) - ord('a')].append(i)

for x in query:
    a, b, c = x.split()
    #print(c)
    if a == '1':
        b = int(b) - 1
        if s[b] == c:
            continue
        d = ord(s[b]) - ord('a')
        e = ord(c) - ord('a')
        temp = bisect_left(p[d], b)
        p[d].pop(temp)
        temp = bisect_left(p[e], b)
        p[e].insert(temp, b)
        s[b] = c
    else:
        b = int(b) - 1
        c = int(c) - 1
        #print(b, c)
        ans = 0
        for i in range(26):
            L = bisect_left(p[i], b)
            if L >= len(p[i]):
                continue
            if p[i][L] <= c:
                ans += 1
        print(ans)
### BUGGY CODE ###

import math
import collections
import numpy as np

def combinations_count(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

c = collections.Counter(A)
ans = 0
for v in c.values():
    if v > 1:
        ans = ans + combinations_count(v, 2)

for i in range(N):
    print(ans + combinations_count(c[A[i]]-1, 2) - combinations_count(c[A[i]], 2))

### FIXED CODE ###

import math
import collections
import numpy as np

def combinations_count(n, r):
    if n <= 1:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

c = collections.Counter(A)
ans = 0
for v in c.values():
    if v > 1:
        ans += v*(v-1)//2

for i in range(N):
    v = c[A[i]]
    print(ans + (v-1)*(v-2)//2 - v*(v-1)//2)
### BUGGY CODE ###

N=int(input())
S=[["" for i in range(N)] for j in range(N)]
for i in range(N):
    s=input()
    for j in range(N):
        S[i][j]=s[j]

ans=0
for i in range(0,N):
    A,B=i,0
    flag=0
    for j in range(0,N):
        for k in range(0,N):
            if S[(k+A)%N][(j+B)%N]!=S[(j+A)%N][(k+B)%N]:
                flag=1
    if flag==0:
        ans+=N

print(ans)


### FIXED CODE ###

N=int(input())
S=["" for j in range(N)]
for i in range(N):
    S[i]=input()

ans=0
for i in range(0,N):
    flag=True
    for j in range(0,N):
        for k in range(0,N):
            flag=flag&(S[(k+i)%N][j]==S[(j+i)%N][k])
    ans+=N*int(flag)

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

from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]

if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0

que = deque()
que.append((0, 0))
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y+1][x] == "#":
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        que.append((y+1, x))
    if x + 1 < w:
        if s[y][x+1] == "#":
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        que.append((y, x+1))
print(dp[h-1][w-1])


### FIXED CODE ###

from collections import deque
h, w =  map(int, input().split())
s = [[i for i in list(str(input()))] for i in range(h)]
INF = 10**9
dp = [[INF for _ in range(w)] for _ in range(h)]


if s[0][0] == "#":
    dp[0][0] = 1
else:
    dp[0][0] = 0
que = deque()
que.append((0, 0))
is_checked = [[False for _ in range(w)] for _ in range(h)]
while len(que) > 0:
    y, x = que.popleft()
    if y + 1 < h:
        if s[y][x] != s[y+1][x]:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x]+1)
        else:
            dp[y+1][x] = min(dp[y+1][x], dp[y][x])
        if not is_checked[y+1][x]:
            que.append((y+1, x))
            is_checked[y+1][x] = True
    if x + 1 < w:
        if s[y][x] != s[y][x+1]:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x]+1)
        else:
            dp[y][x+1] = min(dp[y][x+1], dp[y][x])
        if not is_checked[y][x+1]:
            que.append((y, x+1))
            is_checked[y][x+1] = True
if s[h-1][w-1] == "#":
    dp[h-1][w-1]+=1
print(dp[h-1][w-1]//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


MOD = 10**9+7


def solve2():
    L = input()[:-1]

    int_L = int(L, 2)
    ans = 1  # (0,0)のぶん
    for l in range(1, int_L+1):
        bit_cnt = bin(l).count("1")
        ans += 2**bit_cnt
        ans %= MOD
    print(ans)


solve2()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

MOD = 10**9+7


def solve2():
    L = input()[:-1]
    int_L = int(L, 2)
    ans = 1  # (0,0)のぶん
    for l in range(1, int_L+1):  # 10**6
        bit_cnt = bin(l).count("1")  # 遅そうO(len(bin(l)))
        ans += pow(2, bit_cnt, MOD)
        ans %= MOD
    print(ans)


def solve3():
    L = input()[:-1]
    # dp[smaller?][上からi桁目まで見た] = 何通りあるか?
    dp = [[0]*2 for _ in range(len(L)+1)]
    dp[0][0] = 1  # 0

    for i, c in enumerate(L):
        dp[i+1][0] = dp[i][0]*(int(c)+1)
        dp[i+1][1] = dp[i][1]*3+dp[i][0]*int(c)

        dp[i+1][0] %= MOD
        dp[i+1][1] %= MOD
    print(sum(dp[-1]) % MOD)


solve3()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
from collections import deque
import itertools

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

ans=0
for i in range(K+1):
    l=list(itertools.combinations(range(N-1),i))
    #list(itertools.combinations([1,2,3,4],2))
    # -> [(1,2),(1,3),...,(2,4),(3,4)]
    ans+=(((M*len(l))%MOD )*pow(M-1,N-(i+1),MOD))%MOD

print(ans%MOD)

### FIXED CODE ###

MOD = 998244353


class Combination:
    #modの宣言をする必要がある。
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % MOD
        self.invmod = [1] * (N + 1)
        #逆元?
        self.invmod[N] = pow(self.fac[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % MOD

    def calc(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % MOD * self.invmod[n - k] % MOD


N, M, K = map(int, input().split())
C = Combination(N)

ans = 0
for k in range(K + 1):
    tmp = C.calc(N - 1, N - k - 1) * M * pow(M - 1, N - k - 1, MOD) % MOD
    ans = (ans + tmp) % MOD

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

import sys


def solve(n, a):
    res = -10 ** 20
    for i in range(n, 2 * n + 1):
        l = a[0:i]
        r = a[i:3 * n]
        l.sort(reverse=True)
        r.sort()
        res0 = sum(l[0:n]) - sum(r[0:n])
        if res0 > res:
            res = res0
    return res


# sys.stdin = open('d1.in')
n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))

### FIXED CODE ###

import os
import sys
import heapq


def solve(n, a):
    res = -10 ** 20
    for i in range(n, 2 * n + 1):
        l = a[0:i]
        r = a[i:3 * n]
        l.sort(reverse=True)
        r.sort()
        res0 = sum(l[0:n]) - sum(r[0:n])
        if res0 > res:
            res = res0
    return res


def find_best(n, a):
    h = list()
    s = 0
    best_s = -10**20
    res = list()
    for i in range(0, 2 * n):
        heapq.heappush(h, a[i])
        s += a[i]
        if len(h) > n:
            m = heapq.heappop(h)
            s -= m
        if len(h) == n:
            if best_s < s:
                best_s = s
            res.append(best_s)
    return res


def solve_large(n, a):
    res = -10 ** 20
    max_l = find_best(n, a)
    b = [-x for x in reversed(a)]
    max_r = find_best(n, b)
    max_r.reverse()
    for l, r in zip(max_l, max_r):
        res0 = l + r
        if res < res0:
            res = res0
    return res


input_file = 'd1.in'
if os.path.exists(input_file):
    sys.stdin = open(input_file)
n = int(input())
a = list(map(int, input().split()))
print(solve_large(n, a))
### BUGGY CODE ###

from operator import mul
from functools import reduce
cmb_cnt = {}
def combinations_count(n, r):
    if (n, r) in cmb_cnt:
        return cmb_cnt[(n, r)]
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    cmb_cnt[(n, r)] = numer // denom
    return numer // denom

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

ans = 0
for i in range(len(a_list) - k + 1):
    for j in range(len(a_list) - 1, k + i - 2, -1):
        if(a_list[j] - a_list[i] != 0):
            ans += (a_list[j] - a_list[i]) * combinations_count(j-i-1, k-2)
ans %= 1000000007
print(ans)


### FIXED CODE ###

MOD = 1000000007
# 二項係数
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD

com = COM(100000, MOD)
n, k = map(int, input().split())
a_list = sorted(list(map(int, input().split())))

ans = 0
if k == 1:
    print(0)
else:
    for i in range(1, n+1):
        if i >= k:
            ans += a_list[i-1] * com.calc_COM(i-1, k-1)
        if n-i >= k-1:
            ans -= a_list[i-1] * com.calc_COM(n-i, k-1)
    ans %= MOD
    print(ans)
### BUGGY CODE ###

N=int(input())
ans=0
for i in range(1,N):
    if N%i!=0:
        for j in range(1,N//i+1):
            a=i*j+N-i*j
            if a==N:
                ans+=1
    else:
        for j in range(1,N//i):
            a=i*j+N-i*j
            if a==N:
                ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N):
    if N%i!=0:
        for j in range(1,N//i+1):
            ans+=1
    else:
        for j in range(1,N//i):
            ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [[-INF]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
            continue
        if 0 <= i-2:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])


### FIXED CODE ###

from collections import defaultdict
n = int(input())
A = list(map(int, input().split()))
m = n//2
INF = 10**18
dp = [defaultdict(lambda: -INF) for _ in range(n+1)]
for i in range(1, n+1):
    L = i//2-1
    R = (i+1)//2+1
    for j in range(L, R):
        if j == 1:
            dp[i][j] = max(dp[i-1][j], A[i-1])
        elif 0 <= i-2 and 0 <= j <= m:
            dp[i][j] = max(dp[i-1][j], dp[i-2][j-1]+A[i-1])
print(dp[-1][m])