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

import sys
input=sys.stdin.readline

def main():
    N,M= map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    B = []
    for _ in range(M):
        b,c = map(int,input().split())
        B.append((b,c))
    B.sort(key=lambda x: x[1])

    X = []
    while B:
        b,c = B.pop()
        n = 0
        for a in A:
            if b > n and a < c:
                X.append(c)
                n += 1
        A = A[n:]

    print(sum(X)+sum(A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import bisect

def main():
    _,M= map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    
    B = []
    for _ in range(M):
        b,c = map(int,input().split())
        B.append((b,c))
    B.sort(key=lambda x: x[1])

    x = 0
    m = 0
    while B:
        b,c = B.pop()
        n = bisect.bisect(A,c,lo=m,hi=min(m+b,len(A)))
        x += (n-m)*c
        m = n

    print(x + sum(A[n:]))

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

#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    # bit DP
    N, M = map(int, input().split())
    a, b, c, d = [], [], [], []

    for i in range(M):
        a_, b_ = map(int, input().split())
        c_ = tuple(map(int, input().split()))
        d_ = 0
        for keta in c_:
            d_ |= 1 << keta-1
        a.append(a_)
        b.append(b_)
        c.append(c_)
        d.append(d_)

    DP = [INF]*(2**N)
    DP[0] = 0

    for i in range(M):
        DPnext = DP[:]
        for k in range(2**N):
            DPnext[k | d[i]] = min(DP[k | d[i]], DP[k]+a[i], DPnext[k | d[i]])
        DP = DPnext
    if DP[-1] == INF:
        print(-1)
    else:
        print(DP[-1])
    pass


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
INF = float("inf")


def main():
    # bit DP
    N, M = map(int, input().split())
    a, b, c, d = [], [], [], []

    for i in range(M):
        a_, b_ = map(int, input().split())
        c_ = tuple(map(int, input().split()))
        d_ = 0
        for keta in c_:
            d_ |= 1 << keta-1
        a.append(a_)
        b.append(b_)
        c.append(c_)
        d.append(d_)

    DP = [INF]*(2**N)
    DP[0] = 0

    for i in range(M):
        DPnext = DP[:]
        for k in range(2**N):
            DPnext[k | d[i]] = min(DP[k | d[i]], DP[k]+a[i], DPnext[k | d[i]])
        DP = DPnext
    if DP[-1] == INF:
        print(-1)
    else:
        print(DP[-1])
    pass


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

N = int(input())
A = list(map(int,input().split()))
S = []
import heapq
for i in range(N+1):
    P = A[:(N+i)]
    Q = A[(N+i):]
    for l in range(len(Q)):
        Q[l] *= -1
    heapq.heapify(P)
    heapq.heapify(Q)
    j = 0
    k = 0
    while j < i:
        heapq.heappop(P)
        j += 1
    while k < N-i:
        heapq.heappop(Q)
        k += 1
    s = sum(P) + sum(Q)
    S.append(s)
ans = max(S)
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
S = []
P = A[:N]
Q = A[2*N:]
for i in range(N):
    Q[i] *= -1
R = A[N:2*N]
p = [0]*(N+1)
q = [0]*(N+1)
import heapq
heapq.heapify(P)
heapq.heapify(Q)
sp = sum(P)
sq = sum(Q)
p[0] = sp
q[0] = sq

for i in range(1,N+1):
    heapq.heappush(P,R[i-1])
    x = heapq.heappop(P)
    heapq.heappush(Q,-R[-i])
    y = heapq.heappop(Q)
    sp = sp + R[i-1] - x
    sq = sq - R[-i] - y
    p[i] = sp
    q[i] = sq
ans = -(10**100)
for k in range(N+1):
    ans = max(ans,p[k] + q[N-k])
    
print(ans)
### BUGGY CODE ###

M,K = list(map(int,input().split()))

if M==0:
    if K==0:
        print("0 0")
    else:
        print(-1)
elif M==1:
    if K==0:
        print("0 0 1 1")
    else:
        print(-1)
else:
    if K==0:
        ans = ""
        for i in range(2**M):
            ans = ans+" " +str(i)+" "+ str(i) + " "
        print(ans[:-1])
    elif K<2**M:
        ans = "0 "+str(K)+" 0"
        ansb = str(K)
        for i in range(1,2**M):
            if i!=K:
                ansb = str(i)+ " " +ansb+ " " +str(i)
        ans= ans+" " + ansb
        print(ans)
    else:
        print(-1)

### FIXED CODE ###


M,K = list(map(int,input().split()))

if M==0:
    if K==0:
        print("0 0")
    else:
        print(-1)
elif M==1:
    if K==0:
        print("0 0 1 1")
    else:
        print(-1)
else:
    if K==0:
        ans = []
        for i in range(2**M):
            ans.append(i)
            ans.append(i)
        #ans = list(map(str,ans))
        print(*ans)
    elif K<2**M:
        ans = [0,K,0]
        ansc = []
        for i in range(1,2**M):
            if i!=K:
                ansc.append(i)
                
        ans =ans+ansc + [K] +ansc[::-1]
        #ans = list(map(str,ans))
        print(*ans)
    else:
        print(-1)
### BUGGY CODE ###

N=int(input())
wa=0
for i in range(N,0,-1):
    count=0
    for j in range(1,N+1):
        if(i%j==0):
            count=count+1
    wa=count*i+wa
print(wa)


### FIXED CODE ###



N=int(input())
count=0
for i in range(1,N+1):
    n=N//i
    count=n*(i+i*n)//(2)+count
print(count)
### BUGGY CODE ###

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

max_dice = 0
for i in range(K-1, N):
    tmp_dice = 0
    for j in range(i - K + 1, i + 1):
        tmp_kitai = 0
        for k in range(p[j]):
            tmp_kitai += (k + 1)
        tmp_kitai = tmp_kitai / p[j]
        tmp_dice += tmp_kitai
    if tmp_dice > max_dice:
        max_dice = tmp_dice
print(max_dice)

### FIXED CODE ###

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

dp = [0] * (N)
dp_sub = [0] * (N)

dp[0] = (p[0] + 1) / 2
dp_sub[0] = (p[0] + 1) / 2

for i in range(1, K):
    dp_sub[i] = (p[i] + 1) / 2
    dp[i] = dp[i - 1] + dp_sub[i]

for i in range(K, N):
    dp_sub[i] = (p[i] + 1) / 2
    dp[i] = dp[i - 1] + dp_sub[i] - dp_sub[i-K]
    
print(max(dp))
### BUGGY CODE ###

M = 10 ** 9 + 7

def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    print(solve(a, n))

def solve(a, n):
    if n % 2 == 0:
        for i in range(1, n, 2):
            if a.count(i) != 2:
                return 0
    else:
        if a.count(0) != 1:
            return 0
        for i in range(2, n, 2):
            if a.count(i) != 2:
                return 0

    return modpow(2, n // 2, M)

def modpow(a, b, m):
    r = 1

    while b != 0:
        if b & 0x01:
            r = (r * a) % m
        a = (a * a) % m
        b >>= 1

    return r

main()


### FIXED CODE ###

from collections import Counter

M = 10 ** 9 + 7

def main():
    n = int(input())
    a = [int(s) for s in input().split()]
    print(solve(a, n))

def solve(a, n):
    counter = Counter(a)

    if n % 2 == 0:
        for i in range(1, n, 2):
            if counter.get(i, None) != 2:
                return 0
    else:
        if counter.get(0, None) != 1:
            return 0
        for i in range(2, n, 2):
            if counter.get(i, None) != 2:
                return 0

    return modpow(2, n // 2, M)

def modpow(a, b, m):
    r = 1

    while b != 0:
        if b & 0x01:
            r = (r * a) % m
        a = (a * a) % m
        b >>= 1

    return r

main()
### BUGGY CODE ###

def union_set(x, y):
    lx, x_set = x
    ly, y_set = y
    l = max(lx, ly)
    if lx == ly:
        z_set = x_set.union(y_set)
    else:
        z_set = x_set if lx > ly else y_set
    return [l, z_set]

def update_set(x, t):
    l, s = x
    return [l + len(t), {si + t for si in list(s)}]

s = input()
t = input()
if len(s) < len(t):
    s, t = t, s

table = [[0, {''}] for j in range(len(t) + 1)]
table_pre = [[0, {''}] for j in range(len(t) + 1)]

for i, si in enumerate(s):
    for j, tj in enumerate(t):
        if si == tj:
            table[j + 1] = update_set(table_pre[j], si)
        else:
            table[j + 1] = union_set(table[j], table_pre[j + 1])
    table, table_pre = table_pre, table
print(list(table_pre[-1][1])[0])


### FIXED CODE ###

s = input()
t = input()

table = [[0 for j in range(len(t) + 1)] for i in range(len(s) + 1)]

for i, si in enumerate(s):
    table_pre = table[i]
    table_cur = table[i + 1]
    for j, tj in enumerate(t):
        if si == tj:
            table_cur[j + 1] = table_pre[j] + 1
        else:
            table_cur[j + 1] = max(table_cur[j], table_pre[j + 1])

ls, lt = len(s), len(t)
ans = ''
while ls and lt:
    if table[ls][lt] == table[ls][lt - 1]:
        lt -= 1
    elif table[ls][lt] == table[ls - 1][lt]:
        ls -= 1
    else:
        ans = s[ls - 1] + ans
        ls -= 1
        lt -= 1
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
 
p = list(map(int, input().split()))
s_max = 0
 
for i in range(n-k+1):
  s = sum(p[i:i+k])
  if s_max < s:
    s_max = s
    e = (k+sum(p[i:i+k]))/2
    
print(e)

### FIXED CODE ###

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

m = [(e + 1) / 2 for e in p]

t = sum(m[0:K])
result = t
for i in range(N - K):
    t -= m[i]
    t += m[i + K]
    if t > result:
        result = t
print(result)
### BUGGY CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt

numbers = [1,10, 100, 1000, 10000, 100000, 1000000]
datas = [0,23,473,7053,93643,1166714,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(7):
    if 10 ** i <= N < 10 ** (i+1):
        numPin = i
        break

if numPin != 6:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])


### FIXED CODE ###

def make_divisors(n):
    cnt = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            cnt += 1
            if i != n // i:
                cnt += 1
        i += 1
    return cnt
numbers = [1,10, 100, 1000, 10000, 100000, 150000,200000, 250000,300000,350000, 400000,450000, 500000,550000,600000,630000,675000,700000,720000,750000,800000,825000,850000,875000,900000,912500,925000,950000,975000,987500,1000000]
datas = [0,23,473,7053,93643,1166714, 1810893, 2472071, 3145923, 3829761, 4522005,5221424,5927120,6638407,7354651,8075420,8509899,9164377,9529244,9821778,10261678,10997400,11366472,11736253,12106789,12478098,12664043,12850013,13222660,13595947,13782871,13969985]

N = int(input())
ttl = 0
numPin = 0

for i in range(len(numbers)):
    if N == 1000000:
        numPin = len(numbers) - 1
        break
    if numbers[i] <= N < numbers[i+1]:
        numPin = i
        break

if numPin != len(numbers)-1:
    if N - numbers[numPin] < numbers[numPin + 1] - N:
        for i in range(numbers[numPin], N):
            ttl += make_divisors(i)
        print(ttl + datas[numPin])
    else:
        for i in range(N,numbers[numPin+1]):
            ttl -= make_divisors(i)
        print(ttl + datas[numPin + 1])
else:
    print(datas[numPin])
### BUGGY CODE ###

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

T = ir()

def check(a, b, c, d, i):
    if a < b or d < b:
        print('No')
    else:
        a %= b
        if d > b:
            d %= b
            d += b        
        X = np.array([a] + [d] * 10 ** 5)
        Xcum = (X.cumsum() % b)
        Xcum[Xcum<=c] += d
        bool = np.any(Xcum < b)
        print('No' if bool else 'Yes')

for i in range(T):
    check(*(lr() + [i]))    

# 10

### FIXED CODE ###

import sys
from fractions import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

T = ir()

def check(a, b, c, d):
    if a < b or d < b:
        answer = 'No'
    # 以降 d >= b とする
    elif c >= b:
        answer = 'Yes'
    else:
        a %= b; d %= b
        # c < x < b の間に個数が入ると'No'
        g = gcd(b, d)
        if b - g + (a % g) > c:
            answer = 'No'
        else:
            answer = 'Yes'
    print(answer)

for _ in range(T):
    check(*lr())

# 16
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 10 21:26:22 2019
ABC137D
@author: maezawa
"""

n, m = list(map(int, input().split()))
ab = []
for _ in range(n):
    ai, bi = list(map(int, input().split()))
    ab.append([ai,bi])
    
ab.sort(key=lambda x: x[0])
ab.sort(key=lambda x: x[1], reverse=True)

day = [0]*(m+1)
cnt = 0
for abi in ab:
    if abi[0] <= m:
        i = 0
        while m-abi[0]-i>=0:
            if day[m-abi[0]-i] == 0:
                day[m-abi[0]-i] = 1
                cnt += abi[1]
                break
            i += 1
print(cnt)

    


### FIXED CODE ###

import heapq

n, m = list(map(int, input().split()))
tasks = []
for i in range(n):
    ai, bi = list(map(int, input().split()))
    tasks.append((-bi, i, ai))
tasks.sort(key=lambda x: x[2])    
prtasks = []
money = 0
j = 0
for i in range(1,m+1):
    for k in range(j,len(tasks)):
        if tasks[k][2] <= i:
            heapq.heappush(prtasks, tasks[k])
            j += 1
        else:
            break
    if not prtasks:
        continue
    work = heapq.heappop(prtasks)
    money += work[0]

print(-money)
### BUGGY CODE ###

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

i=1
while 1:
    if (P/i)%int(P/i)==0:
        tmp=pow(P/i,1/N)
        if tmp%int(tmp)==0:
            break
    i+=1
print(int(tmp))

### FIXED CODE ###

import copy
N, P = map(int, input().split())

x=[i+1 for i in range(int(P**(1/2))) if P%(i+1)==0]
for i in range(len(x)):
    if P%x[i]==0:
        x.append(int(P/x[i]))
x.sort(reverse=True)

for i in range(len(x)):
    tmp=round(x[i]**(1/N),10)
    if tmp%int(tmp)==0:
            break

print(int(tmp))
### BUGGY CODE ###

N,M = map(int, input().split())
A = list(map(int, input().split()))
for i in range(M):
    A.sort(reverse=True)
    A[0] = A[0] // 2
print(sum(A))



### FIXED CODE ###

import heapq as hq
N,M = map(int, input().split())
A =[-x for x in map(int, input().split())]

hq.heapify(A)
for i in range(M):
    m = A[0]
    hq.heappushpop(A, -((-m)//2))
print(-sum(A))
### BUGGY CODE ###

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

# 2 boat
boat = 2
ab = []
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    ab.append((a,b))
import numpy as np
ab = np.array(ab)
ok = "IMPOSSIBLE"
for a1 in ab[ab.T[0]==1]:
    # 1 to target N-> ok
  
    for abbb in ab[ab.T[0]==a1[1]]:
        
        if abbb[1] == N:
            ok = "POSSIBLE"
print(ok)

### FIXED CODE ###

import numpy as np
N, M = input().split()
N = int(N)
M = int(M)

# 2 boat
boat = 2
ab = np.zeros(M)
ab1 = []
abN = []
ok = "IMPOSSIBLE"
for i in range(M):
    a,b = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        ab1.append(b)
    elif b == N:
        abN.append(a)
if len(set(abN) & set(ab1))>=1:
    ok = "POSSIBLE"
print(ok)
### BUGGY CODE ###

from bisect import*
n,*a=map(int,open(0).read().split())
l=[0]*n
for i,v in enumerate(a,1):
  l[v-1]=i
b=[0,n+1]
c=0
for i,v in enumerate(l,1):
  j=bisect(b,v)
  c+=(b[j]-v)*(v-b[j-1])*i
  insort(b,v)
print(c)

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

n = int(input())
s = []
a = list(map(int,input().split()))
for x in range(n):
    s.append(a[x])
    s = s[::-1]
print(*s)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if n % 2 == 0:
    a = a[::-2]+a[0::2]
else: a = a[::-2] +a[1::2]
print(*a,sep=" ")
### BUGGY CODE ###

N,M=map(int,input().split())
a=M//N
x=0
for i in reversed(range(1,a+1)):
    if M%i==0:
        x=i
        break
print(x)


### FIXED CODE ###

N,M=map(int,input().split())
a=M//N
x=1
for i in range(1,a+1):
    if M%i==0:
        x=i
        if (M//i)>i and (M//i)<=a:
            x=M//i
            break
print(x)
### BUGGY CODE ###

K, S = map(int,input().split())
count = 0
for x in range(0,K+1,1):
  for y in range(0,K+1,1):
    z = S - x - y
    if x+y+z == S and z <= K and z >= 0:
      count += 1
print(count)

### FIXED CODE ###

K, S = map(int,input().split())
count = 0
for x in range(0,K+1,1):
  for y in range(0,K+1,1):
    if 0<=S-x-y<=K:
      count += 1
print(count)
### BUGGY CODE ###

n,m = map(int,input().split())
A = set()
B = set()
for _ in range(m):
    x = list(map(int,input().split()))
    if x[0]==1:
        A = A|set(x)
    elif x[1]==n:
        B = B|set(x)
if len(A&B)>0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
sa=set()
sb=set()
for i in range(M):
    a,b=map(int,input().split())
    if a==1:sb.add(b)
    if b==N:sa.add(a)
print("IMPOSSIBLE" if len(sa&sb)==0 else "POSSIBLE")
### BUGGY CODE ###

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

dp=[float('inf') for _ in range(n)]
dp[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j<len(dp):
      dp[i+j]=min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
print(dp[-1])

### FIXED CODE ###

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

dp=[float('inf') for _ in range(n)]
dp[0]=0
for i in range(n):
  for j in range(1,k+1):
    if i+j<len(dp):
      dp[i+j]=min(dp[i+j],dp[i]+abs(H[i]-H[i+j]))
print(dp[-1])
### BUGGY CODE ###

N = int(input())
S = list(input())

rS = reversed(S)
cS = [0]
c1 = set()

for i, x in enumerate(rS):
  if x in c1:
    cS.append(cS[i])
  else:
    c1.add(x)
    cS.append(cS[i] + 1)

cS.reverse()

ans = 0
c2 = set()

for i in range(N-2):
  for j in range(i+1, N-1):
    x = S[i] + S[j]
    if x in c2:
      continue
    else:
      c2.add(x)
      ans += cS[j+1]

print(ans)

### FIXED CODE ###

N = int(input())
S = [int(i) for i in input()]

ans = 0

for i in range(10):
  for j in range(10):
    for k in range(10):
      Flag1 = True
      Flag2 = False
      Flag3 = False
      for x in S:
        if Flag3:
          if x == k:
            ans += 1
            break
        if Flag2:
          if x == j:
            Flag2 = False
            Flag3 = True
        if Flag1:
          if x == i:
            Flag1 = False
            Flag2 = True

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

n = int(input())

to_battle_with = [list(map(int, input().split())) for _ in range(n)]

for i in range(n):
    for j in range(n - 1):
        to_battle_with[i][j] -= 1

day_count = 0
remained_battles = (n * (n - 1)) // 2

while remained_battles:
    battled_today = set()

    no_battle_today = True
    for player in range(n):
        if not to_battle_with[player]:
            continue

        next_opponent = to_battle_with[player][0]
        if player in battled_today or next_opponent in battled_today:
            continue

        if not to_battle_with[next_opponent]:
            continue

        if to_battle_with[next_opponent][0] == player:
            battled_today.add(next_opponent)
            battled_today.add(player)
            to_battle_with[player].pop(0)
            to_battle_with[next_opponent].pop(0)
            remained_battles -= 1
            no_battle_today = False
    if no_battle_today:
        print(-1)
        break
    day_count += 1

if not no_battle_today:
    print(day_count)


### FIXED CODE ###

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

to_battle_with = [deque([i - 1 for i in map(int, input().split())]) for _ in range(n)]


def update_battle(player, battle_set, to_battle_with):
    if not to_battle_with[player]:
        return
    next_opponent = to_battle_with[player][0]
    if not to_battle_with[next_opponent]:
        return
    if to_battle_with[next_opponent][0] == player:
        if player > next_opponent:
            player, next_opponent = next_opponent, player
        battle_set.add((player, next_opponent))


battles_today = set()
for player in range(n):
    update_battle(player, battles_today, to_battle_with)

day_count = 0
battle_count = 0
num_all_battles = (n * (n - 1)) // 2

while battles_today:
    battles_tomorrow = set()
    for p1, p2 in battles_today:
        battle_count += 1
        to_battle_with[p1].popleft()
        to_battle_with[p2].popleft()
        for p in [p1, p2]:
            update_battle(p, battles_tomorrow, to_battle_with)
    battles_today = battles_tomorrow
    day_count += 1

if battle_count == num_all_battles:
    print(day_count)
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int,input().split()))
a_list = sorted(a_list)
flag  = [0]*n

ans = 0
for i in range(len(a_list)):
    if flag[i] == 1:
        continue
    if i == n-1:
        ans += 1
        break
    if 0 not in flag:
        break
    flag[i] = 1
    
    if a_list[i] != a_list[i+1]:
        ans += 1
    for j in range(i+1,len(a_list)):
        if a_list[j]%a_list[i] == 0:
            flag[j] = 1

print(ans)

### FIXED CODE ###

n = int(input())
a_list = list(map(int,input().split()))
a_list = sorted(a_list)
flag  = [0]*n


ans = 0
m = max(a_list)
b_list = [0]*(m+1)
for i in a_list:
    b_list[i] += 1
for i in a_list:
    if b_list[i] == 1:
        ans += 1

    for j in range(i , m+1 ,i):
        b_list[j]+= 1
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n, m = map(int, input().split())
a = set()
for _ in range(m):
  a_ = int(input())
  a.add(a_)

dp = [0] * (n+1)
if 1 not in a:
  dp[1] = 1
if 2 not in a and n != 1:
  dp[2] = dp[1] + 1
for i in range(3, n+1):
  if i not in a:
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%(10**9+7))
### BUGGY CODE ###

a,b,x = map(int,input().split())
ans = 0
for i in range(a,b+1):
    if i % x == 0:
        ans += 1
print(ans)

### FIXED CODE ###

a,b,x = map(int,input().split())
if a % x == 0:
    print(b // x - a // x + 1)
else:
    print(b // x - a // x)
### BUGGY CODE ###

_=input()
A=list(map(int,input().split()))
B=list(set(A))
ans=-1
B=sorted(B)[::-1]
for i in B:
  if A.count(i) >=4:
    if ans==-1 : 
      print(i*i)
      exit()
    else:
      print(ans*i)
      exit()
  else:
    if A.count(i) >= 2:
      if ans==-1:
        ans=i
      else:
        print(ans*i)
        exit()
print(0)


### FIXED CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))
A=Counter(A)

S=[]
for i,j in A.items():
  if j>=2:
    S.append(i)
S=list(set(S))
S.sort()
if len(S)>=2:
  ans=S[-1]*S[-2]
else:
  print(0)
  exit()

Q=[]

for i,j in A.items():
  if j>=4:
    Q.append(i)
if Q==[]:
  print(ans)
  exit()
print(max(ans, (max(Q))**2))
### BUGGY CODE ###

K, N = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(len(A)):
    min_this = 0
    for j in range(len(A)-1):
        now_point = A[i+j-len(A)]
        next_point = A[i+j+1-len(A)]
        if next_point - now_point < 0:
            min_this += (K-now_point) + next_point
        else:
            min_this += next_point - now_point
    if i==0:
        total_min = min_this
    else:
        if min_this < total_min:
            total_min = min_this
print(total_min)

### FIXED CODE ###

K, N = list(map(int,input().split()))
A = list(map(int,input().split()))
for i in range(len(A)):
    now_point = A[i]
    last_point = A[i-1]
    if last_point == 0:
        last_point = K
    if last_point - now_point <= 0:
        now_min = (K-now_point) + last_point
    else:
        now_min = last_point - now_point
    if i==0:
        total_min = now_min
    else:
        if now_min < total_min:
            total_min = now_min
print(total_min)