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

from functools import reduce, lru_cache


@lru_cache(maxsize=2**18)
def GCD(x, y):
    if y == 0:
        return x
    else:
        return GCD(y, x % y)


def lcm(x, y):
    return (x * y) // GCD(x, y)


def solve():
    MOD = 10 ** 9 + 7
    N, *A = map(int, open(0).read().split())
    
    lcm_num = reduce(lcm, A)
    ans = 0
    for a in A:
        ans += lcm_num // a
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

    lcm = 1
    for a in A:
        lcm = a * lcm // gcd(a, lcm)

    ans = [lcm // a for a in A]
    print(sum(ans) % MOD)


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

def f(x):
    return x*(x-1)//2

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

d = collections.defaultdict(int)
for i in a:
    d[i]+=1
c = collections.defaultdict(int)
for i in set(a):
    ans=0
    for j in d:
        if j==i:
            ans+=f(d[j]-1)
        else:
            ans+=f(d[j])
    c[i]=ans

for i in a:
    print(c[i])

### FIXED CODE ###

def f(x):
    return x*(x-1)//2

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

d = collections.defaultdict(int)
for i in a:
    d[i]+=1
c = collections.defaultdict(int)
ans=0
for i in set(a):
    ans+=f(d[i])

for i in a:
    print(ans-(d[i]-1))
### BUGGY CODE ###

N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]


def contain(l):
    phase = 0
    for c in S:
        if phase == 0 and c == l[0]:
            phase = 1
            continue
        if phase == 1 and c == l[1]:
            phase = 2
            continue
        if phase == 2 and c == l[2]:
            return 1
    return 0


print(sum(list(map(contain, L))))


### FIXED CODE ###

N = int(input())
S = input()
L = [str(i).zfill(3) for i in range(1000)]
count = 0
for l in L:
    try:
        i = S.index(l[0])
        j = S.index(l[1], i + 1)
        k = S.index(l[2], j + 1)
        count += 1
    except:
        continue
print(count)
### BUGGY CODE ###

# 2020-05-22
from collections import deque


def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    ansers = [0] * n
    for person in range(n):
        stack = deque()
        stack_append = stack.append
        stack_pop = stack.pop
        stack_append(person)
        link = {person}
        link_add = link.add
        while stack:
            new = stack_pop()
            for adj in friends[new]:
                if adj in link:
                    continue
                stack_append(adj)
                link_add(adj)
        # 友達をたどるとブロック対象に着くことがある。積集合 &。
        ans = len(link) - len(friends[person]) - len(link & blocks[person]) - 1
        ansers[person] = ans
    print(*ansers)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 2020-05-22
def main():
    n, m, k = [int(x) for x in input().split()]
    friends = [set() for _ in range(n)]
    blocks = [set() for _ in range(n)]
    for _ in range(m):
        a, b = [int(x) - 1 for x in input().split()]
        friends[a].add(b)
        friends[b].add(a)
    for _ in range(k):
        a, b = [int(x) - 1 for x in input().split()]
        blocks[a].add(b)
        blocks[b].add(a)

    networks = {}  # The dict of networks as sets. Keys are leaders.
    net_leaders = [-1] * n  # The leaders of the networks that the ones joined.
    visited = [False] * n
    for person in range(n):
        if visited[person]:
            continue
        network = set()
        network_add = network.add
        stack = [person]
        stack_append = stack.append
        stack_pop = stack.pop
        while stack:
            new = stack_pop()
            visited[new] = True
            net_leaders[new] = person
            network_add(new)
            for adj in friends[new]:
                if visited[adj]:
                    continue
                stack_append(adj)
        networks[person] = network

    answers = []
    answers_append = answers.append
    for person in range(n):
        net = networks[net_leaders[person]]
        ans = len(net) - len(friends[person]) - 1
        for block in blocks[person]:
            if block in net:
                ans -= 1
        answers_append(ans)

    print(*answers)
    return


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

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

import fractions
l = 1
for val in A:
    l = (l * val // fractions.gcd(val, l))
#print(l)

ans = 0
for val in A:
    ans = (ans + l // val) % MOD
print(ans)



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
import math
M = max(A)
MOD = 10 ** 9 + 7

def power_func(a, n, p):
    res = 1 #これは答え
    while n > 0:
        if n & 1:
            res = res * a % p
        a = a * a % p #1が立っているかどうかに関わらず次のaの累乗を用意しておく
        n = n >> 1
    return res

bucket = [0] * (M + 1)
for val in A:
    for i in range(2, math.floor(math.sqrt(val)) + 1):
        #print(val, i)
        temp = 0
        while val % i == 0:
            val //= i
            temp += 1
        bucket[i] = max(bucket[i], temp)
    if val != 1:
        bucket[val] = max(bucket[val], 1)
#print(bucket)

L = 1
for n in range(M + 1):
    L = (L * n ** bucket[n]) % MOD
#print(L)

ans = 0
for val in A:
    ans = (ans + power_func(val, MOD - 2, MOD))
ans = (ans * L) % MOD
print(ans)
### BUGGY CODE ###

import heapq,sys


def main():
    input = sys.stdin.readline
    X, Y, Z, K = map(int, input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))
    
    #A+Bでのベスト枠K個求めるO(XYlogK)
    AandB = []
    for i in range(X):
        for j in range(Y):
            heapq.heappush(AandB, A[i] + B[j])
            #要素がK+1個以上なら一々はじく！！！ことでO(logK)
            if len(AandB) > K:
                heapq.heappop(AandB)
    #上のとCでのベスト枠K個を求める(ZKlogK)
    heap_queue = []
    for p in range(Z):
        for h in range(len(AandB)):
            heapq.heappush(heap_queue,C[p] + AandB[h])
            if len(heap_queue) > K:
                heapq.heappop(heap_queue)
    heap_queue.sort(reverse = True)
    for e in heap_queue:
        print(e)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,bisect
input = sys.stdin.readline

x,y,z,k = map(int,input().split())
a = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for e in a:
    for w in b:
        ab.append(e+w)
ab.sort()

ok = -1
ng = 10**12
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    cnt = 0
    for e in c:
        cnt += len(ab)-bisect.bisect_left(ab,mid-e)
    if cnt >= k:
        ok = mid
    else:
        ng = mid

res = []
for e in c:
    ind = bisect.bisect_left(ab,ok-e)
    for i in range(ind,len(ab)):
        res.append(e+ab[i])
res.sort()
for i in range(1,k+1):
    print(res[-i])
### BUGGY CODE ###

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

ans=A
for i in range(A, B+1):
  if i==A:
    continue
  ans=ans^i
  
print(ans)

### FIXED CODE ###

#40桁
A,B=map(int, input().split())
#print(bin(A),bin(B))
if A==B:
  print(A)
  exit()
#１が奇数個なら１　偶数こなら０
#2**0 偶奇一致　（A-B）%2==0
#010101010101
#2**1 110011001100...
#2**2 11110000111100001111
ans=0
for i in range(40):
  now=0
  aone=False
  bone=False
  if A>>i&1==1:
    aone=True
  if B>>i&1==1:
    bone=True
  amod=(A)%(2**i)
  bmod=(B)%(2**i)
  #print("amod,bmod",amod, bmod)
  left=(A//(2**i))*(2**i)+amod+1
  right=(B//(2**i))*(2**i)+bmod+1
  base=right-left+1
  #print("left, right", left, right)
  if aone:
    now+=2**i-amod
    base-=2**i-amod
  if bone:
    now+=bmod+1
    base-=bmod+1
  if amod!=bmod:
    now+=(base//(2**i))*2
  now+=((base//(2**i))//2)*2**i
  if now%2==1:
    ans+=2**i
  #print(now)
  
print(ans)
### BUGGY CODE ###

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

t=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z ==s:
                t+=1
print(t)

### FIXED CODE ###

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

t=0
for x in range(k+1):
    for y in range(k+1):
        if s-x-y >= 0 and s-x-y <= k: 
            t+=1
print(t)
### BUGGY CODE ###

info = [int(i) for i in input().split(' ')]
K = info[0]
S = info[1]

count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            ans = x+y+z
            if ans == S:
                count += 1
                
print(count)

### FIXED CODE ###

info = [int(i) for i in input().split(' ')]
K = info[0]
S = info[1]

count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if (0<=z)&(z<=K):
          count += 1
                
print(count)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
ll = list(list(map(int, input().split())) for _ in range(q))

for i in range(q):
    l = ll[i][0]
    r = ll[i][1]
    print(s[l-1:r].count('AC'))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
ll = list(list(map(int, input().split())) for _ in range(q))

acl = [0] * n
cnt = 0
for i in range(1, n):
    if s[i-1:i+1] == 'AC':
        cnt += 1
    acl[i] = cnt

for i in range(q):
    l = ll[i][0]
    r = ll[i][1]
    print(acl[r-1] - acl[l-1])
### BUGGY CODE ###

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

ans = 0
for i in range(len(A)-1):
    tmp = 0
    for j in range(1,len(A)-i):
        # print(A[i],'A[i]',A[i+j],'A[i+j]')
        tmp_ai = A[i] % (10**9 + 7)
        tmp_aij = A[i+j] % (10**9 + 7)
        tmp += tmp_ai * tmp_aij
        # print(tmp,'tmp')
    ans += tmp

ans %= (10**9 + 7)
print(ans)

### FIXED CODE ###

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

sumA = sum(A)
ans = 0
for i in range(len(A)-1):
    sumA -= A[i]
    tmp1 = A[i] % (10**9 + 7)
    tmp2 = sumA % (10**9 + 7)
    ans += tmp1 * tmp2
    ans %= (10**9 + 7)
    
print(ans)
### BUGGY CODE ###

n=int(raw_input())
a=map(int,raw_input().split())
b=[]
for i in range(n):
    b.append(a[i])
    b.reverse()
c=map(str,b)
print ' '.join(c)

### FIXED CODE ###

n=int(raw_input())
a=map(int,raw_input().split())

for i in range((n+1)/2):
    print a[n-2*i-1],
for i in range(n/2):
    print a[i*2+n%2],
print ''
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = a.copy()
from math import gcd

def sieve(n):
    prime = []
    is_prime = [True]*(n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(n+1):
        if is_prime[i]:
            prime.append(i)
            for j in range(i*2, n+1, i):
                is_prime[j] = False
                
    return prime

primes = sieve(1000)
flg = True
for x in primes:
    tmp = 0
    for i in range(n):
        if a[i] % x == 0:
            tmp += 1
        while a[i] % x == 0:
            a[i] //= x
    if tmp > 1:
        flg = False

from collections import Counter
cnt = Counter(a)
for x, c in cnt.items():
    if x != 1 and c > 1:
        flg = False

if flg:
    print('pairwise coprime')
else:
    tmp = b[0]
    for i in range(1, n):
        tmp = gcd(tmp, b[i])
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
import sys
input = sys.stdin.readline

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    for x in res:
        set_primes.add(x)
        
if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

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

tot = []

for l in range(N):
    tot.append(sum([1 for d in S[:l] if d == 'W']) + sum([1 for d in S[l+1:] if d == 'E']))
    
print(min(tot))

### FIXED CODE ###

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

tot = S[1:].count('E')
tot_list = [tot]
former_leader = S[0]

for l in range(1, N):
    leader = S[l]
    if (former_leader, leader)  == ('E', 'E'):
        tot -= 1
    if (former_leader, leader)  == ('W', 'W'):
        tot += 1
        
    former_leader = leader  
    tot_list.append(tot)
    
print(min(tot_list))
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = 1
    for i in range(N):
        ans *= A[i]

    if ans > 10**18:
        ans = -1
    print(ans)
         


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    A = sorted(list(map(int, input().split())))
    ans = 1
    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

import itertools as it

def main():
    N=ii()
    L=lmis()
    ans=0
    for a,b,c in it.combinations(L,3):
        m=max(a,b,c)
        if m<a+b+c-m:
            ans+=1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

import itertools as it

def main():
    N=ii()
    L=sorted(lmis(),reverse=True)

    ans=0
    for i in range(N-2):
        a=L[i]
        j=i+1
        k=N-1
        while j<k:
            if a<L[j]+L[k]:
                j+=1
                ans+=k-j+1
            else:
                k-=1
    
    print(ans)


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

n, m = map(int, input().split())
W, V = [], []
for i in range(n):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
A = [0 for j in range(m+1)]
for i in range(n):
    B = []
    for j in range(W[i-1]):
        B.append(A[j])
    for j in range(W[i-1], m+1):
        B.append(max(A[j], A[j-W[i-1]]+V[i-1]))
    A = B
print(A[m])


### FIXED CODE ###

N, M = map(int, input().split())
W, V = [], []
for n in range(N):
    w, v = map(int, input().split())
    W.append(w)
    V.append(v)
f = [[0 for m in range(M + 1)] for n in range(N + 1)]
for n in range(N):
    for m in range(M + 1):
        if m < W[n]:
            f[n + 1][m] = f[n][m]
        else:
            f[n + 1][m] = max(f[n][m], f[n][m - W[n]] + V[n])
print(f[N][M])
### BUGGY CODE ###

from heapq import heappop,heappush
n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[[]for i in range(n)]
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][1]-a[i][1]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][2]-a[i][2]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
t=[1]*n
t[0],q=0,[]
e=0
for i in s[0]:
    heappush(q,i)
while q and t!=[0]*n:
    b,c,d=heappop(q)
    if t[d] or t[c]:
        if t[d]==1:
            for i in s[d]:
                heappush(q,i)
            t[d]=0
        if t[c]==1:
            for i in s[c]:
                heappush(q,i)
            t[c]=0
        e+=b
print(e)

### FIXED CODE ###

n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

def m():
    H, W = map(int, input().split())
    S = []
    for i in range(H):
        S.append(list(input()))

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = []
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if (a,b) in visited:
                continue
            visited.append((a,b))
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def m():
    H, W = map(int, input().split())
    S = []
    for i in range(H):
        S.append(list(input()))

    graph = [[[]for _ in range(W)] for _ in range(H)]
    visited = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                continue
            if S[max(i - 1, 0)][j] == ".":
                graph[max(i - 1, 0)][j].append((i,j))
                graph[i][j].append((max(i - 1, 0),j))

            if S[min(i+1, H-1)][j] == ".":
                graph[min(i + 1, H - 1)][j].append((i,j))
                graph[i][j].append((min(i + 1, H - 1),j))

            if S[i][max(j - 1, 0)] == ".":
                graph[i][max(j - 1, 0)].append((i,j))
                graph[i][j].append((i,max(j - 1, 0)))

            if S[i][min(j+1, W-1)] == ".":
                graph[i][min(j + 1, W - 1)].append((i,j))
                graph[i][j].append((i,min(j+1, W-1)))

    bw = [0] * 2
    def dfs(g):
        for a,b in g:
            if visited[a][b] == 1:
                continue
            visited[a][b] = 1
            if S[a][b] == ".":
                bw[0] += 1
            else:
                bw[1] += 1
            dfs(graph[a][b])

    ans = 0
    for i in range(H):
        for j in range(W):
            if visited[i][j] == 1:
                continue
            bw[0], bw[1] = 0, 0
            dfs(graph[i][j])
            ans += bw[0] * bw[1]

    return ans

print(m())
### BUGGY CODE ###

a,b,c,d=map(int,input().split())
p=[[0]*(d+2)for i in range(c+1)]
p[a][b]=1
m=998244353
for i in range(a,c+1):
 for j in range(b,d+1):p[i][j]+=(j*p[i-1][j]+i*p[i][j-1]-(i-1)*(j-1)*p[i-1][j-1])%m;p[i][j]%=m
print(p[-1][-2]%m)

### FIXED CODE ###

a,b,c,d=map(int,input().split())
p=[[0]*(d+2)for i in range(c+1)]
p[a][b]=1
m=998244353
for i in range(a,c+1):
 for j in range(b,d+1):p[i][j]+=(j*p[i-1][j]+i*p[i][j-1]-(i-1)*(j-1)*p[i-1][j-1])%m;p[i][j]%=m
print(p[-1][-2]%m)
### BUGGY CODE ###

from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<=x<j
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        que.append((state[c-1],i+1))
        state[c-1]=i+1

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

seg=BIT(N+1)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    now=que[i]
    l, r=now  # index
    #A[l]+=1
    seg.add(l, 1)

    while query and query[-1][1]==r:
        lq,rq,j=query.pop()
        
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.query(lq,rq+1))
        #print(seg.get(lq,rq+1))

while query:
    lq,rq,j=query.pop()   
    ans[j]=rq-lq+1-(seg.get(lq-1,rq))
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)


### FIXED CODE ###

from collections import deque
N,Q=map(int, input().split())

#重複分を引く

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # I: idx(base: 1), x: value
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
            
    # i<x<=j 
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

query=[]

C=list(map(int, input().split()))
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l,r,i))
query=sorted(query, key=lambda x: -x[1])

state=[-1]*N
seg=BIT(N+1)
ans=[0]*Q

for i in range(N):
    while query and query[-1][1]<i+1:
        l,r,j=query.pop()
        ans[j]=r-l+1-(seg.get(l-1,r))

    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i+1
    else:
        idx=state[c-1]
        seg.add(idx,1)
        state[c-1]=i+1
    while query and query[-1][1]==i+1:
        lq,rq,j=query.pop()
        ans[j]=rq-lq+1-(seg.get(lq-1,rq))
        #print(lq, rq, seg.get(lq-1,rq))



for a in ans:
    print(a)
### BUGGY CODE ###

n = int(input())
p = list(map(int, input().split()))
cnt = n
for i in range(n):
    if not all(p[i]<=p[j] for j in range(i+1)):
        cnt -= 1
print(cnt)

### FIXED CODE ###

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

cnt = 0
m = 10**6
for i in p:
    if i < m:
        m = i
        cnt += 1
print(cnt)
### BUGGY CODE ###

n,q=map(int,input().split())
s=list(input())
value=[0]
ans_list=[]
length=[]
s_length=len(s)

for i in range(s_length-1):
  if s[s_length-i-1]=='C' and s[s_length-i-2]=='A':
    value.insert(0,value[0]+1)
  else:
    value.insert(0,value[0])

for i in range(q):
  l,r=map(int,input().split())
  print(value[l-1]-value[r-1])

### FIXED CODE ###

N, Q=map(int,input().split())
S=input()
t=[0]*(N+1)
for i in range(N):
  t[i+1]=t[i]+(1 if S[i : i+2]== 'AC' else 0)
for i in range(Q):
  l, r=map(int,input().split())
  print(t[r-1]-t[l-1])