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

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

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

#print(N,Q,S)
#print(lr)

#print(S[0:5])

for _ in range(Q):
    l = lr[_][0]
    r = lr[_][1]
    #print(_,S[0:r],S[0:(l-1)])
    print(S[0:r].count('AC')-S[0:l].count('AC'))

### FIXED CODE ###

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

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

#print(N,Q,S)
#print(lr)

#print(S[0:5])

CC=[0]
for _ in range(1,N):
    if (S[_-1:_+1] == 'AC'):
        CC.append(CC[_-1]+1)
    else:
        CC.append(CC[_-1])

    #CC.append(S[0:_].count('AC'))

#print(CC)

for _ in range(Q):
    l = lr[_][0]
    r = lr[_][1]

    print(CC[r-1]-CC[l-1])

#for _ in range(Q):
#    l = lr[_][0]
#    r = lr[_][1]
    #print(_,S[0:r],S[0:(l-1)])
    #print(S[0:r].count('AC')-S[0:l].count('AC'))
    #print(_,S[l-1:r])
#    print(S[l-1:r].count('AC'))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M, P = map(int, readline().split())
ABC = [[int(x) for x in readline().split()] for _ in range(M)]

'''
PATH = [[] for _ in range(N+1)]
for _ in range(M):
    a, b, c = map(int, readline().split())
    PATH[a].append((b, c))
'''

INF = 10 ** 12
POINT = [INF] * (N + 1)

POINT[1] = 0

for i in range(N):
    update = False
    for j in range(M):
        a, b, c = ABC[j]
        pt = P - c
        if POINT[a] != INF and POINT[a] + pt < POINT[b]:
            POINT[b] = POINT[a] + pt
            update = True

            if i == N - 1 and b == N:
                print(-1)
                exit()

    if not update:
        break

pt = -POINT[N]

ans = pt if pt > 0 else 0
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N, M, P = map(int, readline().split())

EDGES = []
TO = [[] for _ in range(N + 1)]
RTO = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b, c = map(int, readline().split())
    EDGES.append((a, b, c))
    TO[a].append(b)
    RTO[b].append(a)

# 1から到達可能な点
REACH_FROM_1 = [False] * (N+1)
q = [1]
while q:
    u = q.pop()
    if REACH_FROM_1[u]:
        continue
    REACH_FROM_1[u] = True
    for v in TO[u]:
        q.append(v)

# Nから到達可能な点
REACH_TO_N = [False] * (N + 1)
q = [N]
while q:
    u = q.pop()
    if REACH_TO_N[u]:
        continue
    REACH_TO_N[u] = True
    for v in RTO[u]:
        q.append(v)

STATE = [REACH_FROM_1[i] & REACH_TO_N[i] for i in range(N + 1)]


INF = 10 ** 12
POINT = [INF] * (N + 1)

POINT[1] = 0

for i in range(N):
    update = False
    for j in range(M):
        a, b, c = EDGES[j]
        if not STATE[a]:
            continue
        pt = - (c - P)
        if POINT[a] != INF and POINT[a] + pt < POINT[b]:
            POINT[b] = POINT[a] + pt
            update = True

            if i == N-1:
                print(-1)
                exit()

    if not update:
        break

# print(POINT)
pt = -POINT[N]

ans = pt if pt > 0 else 0
print(ans)
### BUGGY CODE ###

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

count = {}
for i in range(N):
  if a[i] in count.keys():
	  count[a[i]] += 1
  else:
      count[a[i]] = 1

del_cnt = 0
for num in count:
  if num < count[num]:
    del_cnt += (count[num] - num)
  elif num > count[num]:
    del_cnt += count[num]

print(del_cnt)

### FIXED CODE ###

from collections import Counter
N = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)

ans = 0
for i in cnt:
  if cnt[i] > int(i):
      ans += cnt[i] - int(i)
  elif int(i) > cnt[i]:
      ans += cnt[i]

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

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

count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i + j + k == S:
                count += 1

print(count)

### FIXED CODE ###

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

count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if z <= K and z >= 0:
            count += 1

print(count)
### BUGGY CODE ###

import numpy as np

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

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)

a.sort()
f.sort()
f=f[::-1]
af=a*f

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return (np.maximum(0,(af-r+f-1)//f)).sum()<=k
    
m=-1
M=10**12

while True:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        if m==pos:#終わり
            print(M)
            break
        m=pos



### FIXED CODE ###

import numpy as np

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

a=np.array(input().split(),dtype=np.int64)
f=np.array(input().split(),dtype=np.int64)

a.sort()
f.sort()
f=f[::-1]
af=a*f

# r以下にするのに必要修行回数がk以内かどうか
def safe(r):
    return (np.maximum(0,(af-r+f-1)//f)).sum()<=k
    
m=-1
M=10**12

while m+1<M:
    pos=(m+M)//2
    if safe(pos):
        M=pos
    else:
        m=pos
print(M)
### BUGGY CODE ###


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

from fractions import gcd
import math
from collections import Counter
from itertools import combinations

def trial_division(n):
    if n == 1: return []
    
    result = []
    
    for k in range(2, n):
      while n % k == 0:
        n //= k
        result.append(k)

    if not result:
      result.append(n)
      return result
    else:
      return result

G = gcd(A, B)
if G == 1:
  print(1)
  exit()

D = [1] + list(Counter(trial_division(G)).keys())
print(len(D))

### FIXED CODE ###


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

from fractions import gcd
import math
from collections import Counter
from itertools import combinations

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

G = gcd(A, B)
if G == 1:
  print(1)
  exit()

D = [1] + list(Counter(prime_factorize(G)).keys())
print(len(D))
### BUGGY CODE ###

n,x = open(0).read().splitlines()

n = int(n)
size = len(x)
x = int(x,2)

from collections import defaultdict

#count
d = {0:0}

def calc(n):
    if n not in d:
        pop = n % f'{n:b}'.count('1')
        d[n] = calc(pop) + 1
    return d[n]

for i in range(n):
    m = x ^ (1<<(size-i-1))
    print(calc(m))

### FIXED CODE ###

from sys import exit
from collections import defaultdict
n,x = open(0).read().split()
n = int(n)
cnt = x.count('1') 
digits = list(map(int, list(x)))
x = int(x, 2)

d = defaultdict(int)
d[0] = 0
def calc(m):
    if m not in d:
        nxt = m % bin(m).count('1')
        d[m] = calc(nxt) + 1
    return d[m]

if n == 1:
    print(calc(x^1))
    exit()

mmod = cnt - 1
pmod = cnt + 1

if mmod > 0:
    mx = x % mmod
px = x % pmod

mbase = 1
pbase = 1

ans = []
while digits:
    digit = digits.pop()
    
    if digit and mmod <= 0:
        ans.append(0)
    else:
        if digit:
            nx = (mx - mbase)%mmod
        else:
            nx = (px + pbase)%pmod
        ans.append(calc(nx) + 1)

    if mmod > 0:
        mbase = (mbase * 2) % mmod
    pbase = (pbase * 2) % pmod

while ans:
    print(ans.pop())
### BUGGY CODE ###

# input
N = int(input())

Cap = []
append = Cap.append
for i in range(5):
    append(int(input()))

# check
total = 0
citys = [N] + ([0] * 5)

while citys[5] != N:
    for i in range(5, 0, -1):

        if 0 < citys[i - 1] <= Cap[i - 1]:
            mov = citys[i - 1]
            citys[i] += mov
            citys[i - 1] = 0
        elif citys[i - 1] > Cap[i - 1]:
            mov = Cap[i - 1]
            citys[i] += mov
            citys[i - 1] -= mov
        else:
            pass
    total += 1

print(total)

### FIXED CODE ###

# input
N = int(input())

Cap = []
append = Cap.append
for i in range(5):
    append(int(input()))

# check
total = 0
citys = [N] + ([0] * 5)

bottleneck = min(Cap)
print((N + bottleneck - 1) // bottleneck + 4)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array([int(a) for a in input().split()])
q = int(input())
bc = np.array([[int(a) for a in input().split()] for j in range(q)])

u, c = np.unique(a, return_counts=True)
dica = dict(zip(u, c))
#print(dica)

keys = dica.keys()

for i in range(q):
  t1, t2 = bc[i]
  if not t1 in keys:
    dica[t1] = 0
    
  if not t2 in keys:
    dica[t2] = 0


for i in range(q):
  t1, t2 = bc[i]
  dica[t2] = dica[t1] + dica[t2]
  dica[t1] = 0
  print(sum([ k*dica[k] for k in dica.keys()]))






### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array([int(a) for a in input().split()])
q = int(input())
bc = np.array([[int(a) for a in input().split()] for j in range(q)])

u, c = np.unique(a, return_counts=True)
dica = dict(zip(u, c))
#print(dica)

keys = dica.keys()

tmp = sum([ k*dica[k] for k in dica.keys()])


for i in range(q):
  t1, t2 = bc[i]
  if not t1 in keys:
    dica[t1] = 0
  if not t2 in keys:
    dica[t2] = 0

  tmp += dica[t1] * (t2 - t1)
  print(tmp)
  
  dica[t2] = dica[t1] + dica[t2]
  dica[t1] = 0
### BUGGY CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]]:
                tree2.add(pos[c[i]], -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(min(x,int(k*1.4))):
    for j in range(min(y,int(k*1.4))):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(w):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)


### FIXED CODE ###

x,y,z,k = map(int, input().split())
a = sorted(map(int, input().split()), reverse=True)
b = sorted(map(int, input().split()), reverse=True)
c = sorted(map(int, input().split()), reverse=True)

d = []
for i in range(min(x,int(k*1.4))):
    for j in range(min(y,int(k*1.4))):
        d.append(a[i]+b[j])

d = sorted(d, reverse=True)
d = d[0:min(k,len(d))]
w = len(d)

e = []
for i in range(min(k,z)):
    for j in range(w):
        e.append(c[i]+d[j])

e = sorted(e, reverse=True)
for f in e[0:k]:
    print(f)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

N=int(input())
A=list(map(int,input().split()))
org_A=A[:]
#左から最大公約数作る右もね
ans=0
for i in range(N):
    l=A[:i]
    for j in range(len(l)-1):
        l[j+1]=euclid(l[j+1],l[j])
    
    r=A[i+1:]
    for j in range(len(r)-1):
        r[-j-2]=euclid(r[-j-1],r[-j-2])
        
    ans=max(ans,euclid(r[0] if len(r)>0 else l[-1],l[-1] if len(l)>0 else r[0]))
    
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def euclid(a,b):
    a,b=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        a,b=b,a%b
        return euclid(a,b)

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

org_A=A[:]
#左から最大公約数作る右もね
A=A[::-1]
l=[A.pop(-1)]
while A:
    l.append(euclid(l[-1],A.pop(-1)))

A=org_A
r=[A.pop(-1)]
while A:
    r.append(euclid(r[-1],A.pop(-1)))
r=r[::-1]

ans=0
#print(l,r)
for i in range(N):
    temp=euclid(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    #print(l[i-1] if i!=0 else r[i+1],r[i+1] if i!=N-1 else l[i-1])
    ans=max(ans,temp)

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

N=int(input())
P=[None]*N
for i in range(N):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

ZOUKA=[0]*(N+1)

for i in range(1,N+1):
    if ZOUKA[i]==-1:
        continue
    
    r=i
    for j in range(N):
        if P[j]==r:
            r+=1
            ZOUKA[i]+=1
            break

    for k in range(j+1,N):
        if P[k]==r:
            ZOUKA[r]=-1
            r+=1
            ZOUKA[i]+=1

Ans=N-max(ZOUKA)
print(Ans)

### FIXED CODE ###

N=int(input())
P=[None]*(N+1)
for i in range(1,N+1):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

Q=[0]*(N+2)

for i in range(1,N+1):
    Q[P[i]]=i

count=0
Ans=0
for i in range(1,N+2):
    if Q[i]>Q[i-1]:
        count+=1
    else:
        Ans=max(count,Ans)
        count=1

print(N-Ans)
### BUGGY CODE ###

import numpy as np
n,m,k = list(map(int, input().split()))
a_list = np.array(input().split()).astype(int)
b_list = np.array(input().split()).astype(int)
ans_list=[]
for i in range(n+1):
    for l in range(m+1):
        if sum(a_list[:i]) + sum(b_list[:l]) <= k:
            ans_list.append(i+l)
            

print(max(ans_list))

### FIXED CODE ###

import numpy as np
n,m,k = list(map(int, input().split()))
a_list = np.array(input().split()).astype(int)
b_list = np.array(input().split()).astype(int)
a_sum =[0]
b_sum=[0]
for i in range(n):
    a_sum.append(a_sum[-1]+ a_list[i])
for i in range(m):
    b_sum.append(b_sum[-1] + b_list[i])
#print(a_sum, b_sum)
total = 0
num = m

for i in range(n+1):
    
    if a_sum[i] > k:
        break
    while (k - a_sum[i]) < b_sum[num]:
        num -=1
        #print(i, num)
        if num == -1:
            break
    total = max(i+num, total)
    
    
print(total)
### BUGGY CODE ###

N = int(input())

S = []

for i in range(N):
  S.append(str(input()))

cnt_ar = list(set(S))
cnt_ar.sort()

length = len(cnt_ar)

ar = [0 for i in range(length)]

for i in range(length):
  ar[i] = S.count(cnt_ar[i])

max_num = max(ar)

for i in range(len(ar)):
  if ar[i] == max_num:
    print(cnt_ar[i])


### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
    S = input()
    if S in d:
        d[S] += 1
    else:
        d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
    print(s)
### BUGGY CODE ###


s= input()
t = input()

def swap(S, a,b):
    ss = ""
    for s in S:
        if s == a:
            ss += b
        elif s == b:
            ss += a
        else:
            ss += s
    return ss
        
def solve(S,T):
    s_copy = S
    t_copy = T
    char_map = set()
    for i in range(len(S)):
        s = S[i]
        t = T[i]
        if s != t:
            char_map.add((s,t))
            S = swap(S, s,t)
    return S == T


    

if solve(s,t):
    print("Yes") 
else:
    print("No")



### FIXED CODE ###


s= input()
t = input()






def solve(S,T):
    s_map  = {}
    t_map = {}

    for s in S:
        if s in s_map:
            s_map[s] += 1
        else:
            s_map[s] = 1

    
    for t in T:
        if t in t_map:
            t_map[t] += 1
        else:
            t_map[t] = 1

    s_l = []
    t_l = []

    for sss in s_map:
        s_l.append(s_map[sss])
    for ttt in t_map:
        t_l.append(t_map[ttt])

    return sorted(s_l) == sorted(t_l)


    

if solve(s,t):
    print("Yes") 
else:
    print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
import bisect

# 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():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            idx_target = ord(S[y]) - ord("a")
            idx_del = bisect.bisect_left(L[idx_target], y)
            if idx_del < len(L[idx_target]):
                L[idx_target].pop(idx_del)
            bisect.insort(L[ord(z) - ord("a")], y)
            S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import bisect

# 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():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            if S[y] != z:
                idx_target = ord(S[y]) - ord("a")
                idx_del = bisect.bisect_left(L[idx_target], y)
                if idx_del < len(L[idx_target]):
                    L[idx_target].pop(idx_del)
                bisect.insort(L[ord(z) - ord("a")], y)
                S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(26):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

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

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

ans = 0
for a in set(A):
    count = A.count(a)
    if count > a:
        ans += count - a
    elif count < a:
        ans += count

print(ans)

### FIXED CODE ###

import collections

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

c = collections.Counter(a)

ans = 0
for i, m in c.items():
    if m < i:
        ans += m
    else:
        ans += m - i
print(ans)
### BUGGY CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
check = [False] * n
ans = 0
for i in range(n):
    if check[i]:
        continue
    FLAG = True
    for j in range(i + 1, n):
        if check[j]:
            continue
        if FLAG and a[j] == a[i]:
            FLAG = False
            ans -= 1
        if a[j] % a[i] == 0:
            check[j] = True
    ans += 1
print(ans)


### FIXED CODE ###

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = sorted(inpl())
cnt = collections.Counter(a)
ans = 0
dp = [0] * (10**6 + 1)
for i in a:
    if dp[i] == 0:
        for j in range(1, 10**7):
            if i * j > 10**6:
                break
            dp[i * j] = 1
        if cnt[i] == 1:
            ans += 1
print(ans)
### BUGGY CODE ###

N , M = map(int, input().rstrip().split())
 
pricelist = list(map(int, input().split()))
#moneylist = input().rstrip().split()
#pricelist.append(price)
 
for i in range(M):
  pricelist.sort()
  pricelist[N-1] = pricelist[N-1] // 2

print(sum(pricelist)) 

### FIXED CODE ###

import heapq
N , M = map(int, input().rstrip().split())
 
pricelist = list(map(int, input().split()))
for i in range(N):
  pricelist[i] = pricelist[i] * (-1)
heapq.heapify(pricelist)

 
for i in range(M):
  minprice = heapq.heappop(pricelist)
  if minprice % 2 == 0:
    minprice = minprice // 2
  else:
    minprice = minprice // 2 + 1
  heapq.heappush(pricelist, minprice)

print(sum(pricelist)* (-1))
### BUGGY CODE ###

from sys import stdin
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    m=n//2
    a=list(map(int,readline().split()))

    s=sum(a)//2
    ans=[0]*n
    k=n-1
    for i in range(n):
        t=0
        for j in range(m):
            t+=a[i]
            i+=2
            i%=n
        ans[k]=(s-t)*2
        k+=1
        k%=n

    print(*ans)

if __name__=="__main__":
    main()

### FIXED CODE ###

def main():
    N=int(input())
    A=list(map(int,input().split()))
    w=sum(A)
    if N==3:
        li=[]
        for i in range(1,N):
            li.append(w-2*A[i])
        li.append(w-2*A[0])
        result=" ".join(map(str,li))
        print(result)
    else:
        li=[0]*N
        n=N//2
        count=0
        for j in range(1,2*n+1,2):  #w_1を先に求める
            count+=2*A[j]
        li[0]=w-count
        
        for i in range(N-1):  #漸化式を用いて残りを求める
            li[i+1]=2*A[i]-li[i]

        result=" ".join(map(str,li))
        print(result)
if __name__=="__main__":
    main()
### BUGGY CODE ###

N=int(input())
a=list(map(int,input().split()))
cnt=0
k=0
for i in range(N):
    if i+1 in a[k:N]:
        for j in range(k,N):
            if a[j]==i+1:
                cnt+=1
                k=j
                break
    else:
        break
print(N-cnt if cnt>0 else -1)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
cnt=0
for i in range(N):
    if a[i]==cnt+1:
        b[i]=1
        cnt+=1
print(N-sum(b) if sum(b)>0 else -1)