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

n, q = map(int, input().split())
s = input()
arr = [list(map(int, input().split())) for i in range(q)]


for left, right in arr:
    word = s[left - 1: right]
    ans = word.count('AC')
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
num = [list(map(int, input().split())) for i in range(q)]
arr = [0]
tmp = 0
for i in range(n):
    if s[i:i+2] == 'AC':
        tmp += 1
    arr.append(tmp)

for left, right in num:
    ans = arr[right - 1] - arr[left - 1]
    print(ans)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            if ll[i] < ll[j] + ll[k] and ll[j] < ll[k] + ll[i] and ll[k] < ll[i] + ll[j]:
                ans += 1

print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!

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

ll.sort()
ans = 0
for i in range(n - 2):
    for j in range(i+1, n - 1):
        lb = j + 1
        ub = n - 1
        b = ll[i] + ll[j]
        if ll[lb] >= b:
            continue
        if ll[ub] < b:
            ans += ub - lb + 1
            continue
        while True:
            if ub == lb:
                ans += ub - j
                break
            t = (lb + ub) // 2 + 1
            if ll[t] < b:
                lb = t
            else:
                ub = t - 1
print(ans)
### BUGGY CODE ###

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

ns = list()
first = 1
for i in range(K):
    first *= scores[i]
ns.append(first)
for i in range(0, N-K):
    ns.append(ns[i] * scores[i+K] // scores[i])
    if ns[i] < ns[i+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

for i in range(K, N):
    if scores[i] > scores[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

dp = [[0]*1000 for _ in range(N+1)]
s = set([(1000, 0)])

money = 1000
for i in range(N):
    s = list(s)
    a = As[i]
    nx = set()
    for m, num in s:
        m2 = m
        cnt = 0
        while m2>=0:
            nx.add((m2, num+cnt))
            m2 -= a
            cnt += 1
        for n in range(1, num+1):
            nx.add((m+a*n, num-n))
    s = nx

lis = list(nx)
lis.sort()
print(lis[-1][0])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

memo = {}
s = set()

ans = 0
def dfs(idx, money, stocks):
    global ans
    if idx==N:
        ans = max(ans, money)
        return
    a = As[idx]
    if (idx, stocks) in s:
        if money<=memo[(idx, stocks)]:
            return
    s.add((idx, stocks))
    memo[(idx, stocks)] = money
    dfs(idx+1, money+stocks*a, 0)
    dfs(idx+1, money, stocks)
    cnt = money//a
    dfs(idx+1, money-cnt*a, stocks+cnt)

dfs(0, 1000, 0)
print(ans)
### BUGGY CODE ###

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

def ea(a, b) :
    if a%b == 0 :
        return b
    else :
        return ea(b, a%b)

def gcd(list1) :
    global dol
    lngt = len(list1)
    tuple1 = tuple(list1)
    if tuple1 in dol.keys() :
        return dol[tuple1]
    elif lngt == 1 :
        return list1[0]
    else :
        rt = ea(gcd(list1[:lngt//2]), gcd(list1[lngt//2:]))
        dol[tuple1] = rt
        return rt

dol = {}
anslist = []
for n in range(N) :
    anslist.append(gcd(Alist[:n]+Alist[n+1:]))
print(max(anslist))

### FIXED CODE ###

from functools import lru_cache
n = int(input())
aa = list(map(int, input().split()))

@lru_cache(maxsize=10**9)
def gcd(a, b) :
    if b == 0 : return a
    elif a%b : return gcd(b, a%b)
    else : return b

l = [0]
r = [0]
for i in range(n) :
    l.append(gcd(l[-1], aa[i]))
    r.append(gcd(r[-1], aa[-i-1]))

m = [gcd(l[i],r[-i-2]) for i in range(n)]
print(max(m))
### BUGGY CODE ###

#ABC116D-VariousSushi.py

INPUT1 = [int(n) for n in input().split()]

N, K = INPUT1[0], INPUT1[1]
Parameters = []
Score, Test = 0, 0
flag1, flag2 = 0, 0
kind = []
kindnumber = 0

ParametersAppend = Parameters.append
for i in range(N):
    INPUT2 = [int(m) for m in input().split()]
    ParametersAppend([INPUT2[0], INPUT2[1]])

Parameters = sorted(Parameters, key=lambda x: x[1], reverse=True)

def binanrySearch(kind, target):
    testkind = kind[:]
    testkind.sort()
    left, right = 0, len(testkind)-1
    while(right >= left):
        mid = int((right + left) / 2)
        if testkind[mid] == target:
            return True
        elif testkind[mid] > target:
            right = mid - 1
        elif testkind[mid] < target:
            left = mid + 1
    return False

def SumScore(List, K, kindnumber):
    taste = 0
    for i in range(K):
        taste += List[i][1]
    return taste + kindnumber * kindnumber

def SearchNew(List, K, kind):
    newkind = -1
    for i in range(len(List)-K):
        if binanrySearch(kind, List[K+i][0]) == False:
            newkind = K+i
            break
    return newkind

def SearchDouble(List, K, kind):
    result = -1
    testkind = kind[:]
    testkindPop = testkind.pop
    for i in range(K):
        testkindPop(K-1-i)
        if binanrySearch(testkind, List[K-1-i][0]) == True:
            result = K-1-i
            break
    return result

kindAppend = kind.append

for i in range(K):
    kindAppend(Parameters[i][0])
kindnumber = len(set(kind))
Score = SumScore(Parameters, K, kindnumber)
kind.clear()

for t in Parameters:
    for i in range(K):
        kindAppend(Parameters[i][0])
    kindnumber = len(set(kind))
    i = SearchNew(Parameters, K, kind)
    j = SearchDouble(Parameters, K, kind)
    Parameters[i], Parameters[j] = Parameters[j], Parameters[i]
    if i != -1 and j != -1:
        kindnumber += 1
    else:
        break
    Test = SumScore(Parameters, K, kindnumber)
    if Score <= Test:
        Score = Test
    kind.clear()

print(Score)


### FIXED CODE ###

#ABC116D-VariousSushi.py

from sys import stdin
#from numpy import sum

input = stdin.readline

N, K = list(map(int, input().split()))
List1= []
kind = set()
point1, point2 = 0, 0

INPUT = [tuple(map(int, input().split())) for _ in range(N)]

INPUT.sort(key = lambda x: -x[1])

for ti, di in INPUT[:K]:
    point1 += di
    if ti in kind:
        List1.append(di)
    kind.add(ti)

point2 = len(kind)

Score = point1 + point2**2
Test = Score

List1POP = List1.pop

for ti, di in INPUT[K:]:
    if 0 >= len(List1):
        break
    if ti in kind:
        continue
    Test = Test - List1POP() + di + 2 * point2 + 1
    point2 += 1
    kind.add(ti)
    Score = max(Score, Test)

print(Score)
### BUGGY CODE ###

import math

N = int(input())
n = int(math.sqrt(N))

while n<= N:
  if(N % n == 0):
    break
  else:
    n += 1
    
print(len(str(n)))

### FIXED CODE ###

import math

N = int(input())
n = 1
divisor = []

while n*n<= N:
  if(N % n == 0):
    divisor.append(n)
  n+= 1
  
max_divisor = divisor[-1]

print(len(str(N// max_divisor)))
### BUGGY CODE ###

from collections import deque
def bfs(maze, visited, l):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if all ([-1 not in i for i in visited]):
            s=set()
            for i in visited:
                s.add(max(i))
            return(max(s))
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])

print(bfs(maze, visited,l_b))

### FIXED CODE ###

from collections import deque
def bfs(maze, visited, l,n_w):
    queue = deque(l)
    for i in queue:
        visited[i[0]][i[1]] = 0
    while queue:
        y, x = queue.popleft()
        if n_w==0:
            s=set()
            tmp=0
            for i in visited:
                if max(i)>tmp:tmp=max(i)
            return(tmp)
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                queue.append([new_y, new_x])
                n_w-=1

R, C = map(int, input().split())


maze = ["$"*(C+2)]+["$"+input()+"$" for i in range(R)]+["$"*(C+2)]
visited = [[-2]*(C+2)]+[[-2]+[-1]*(C)+[-2] for j in range(R)]+[[-2]*(C+2)]
l_b=[]
for i in range(R+2):
    for j in range(C+2):
        if maze[i][j]=="#":
            l_b.append([i,j])
n_w=R*C-len(l_b)

print(bfs(maze, visited,l_b,n_w))
### BUGGY CODE ###

from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
for i in range(1, len(s)+1):
    a[int(s[:i][::-1])%2019] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    ans += comb(x)
print(ans)

### FIXED CODE ###

from collections import Counter, defaultdict
a = defaultdict(int)
a[0] += 1
s = input()[::-1]
cur = 0
for i, x in enumerate(s):
    cur += (int(x)*pow(10, i, 2019))%2019
    cur %= 2019
    a[cur] += 1

def comb(a):
    return a*(a-1)//2

ans = 0
for x in a.values():
    if x >= 2:
        ans += comb(x)
print(ans)
### BUGGY CODE ###

#累積xor
#累積和

N = int(input())
A = [0] + list(map(int,input().split()))

#累積xor
ruiseki_xor = [A[i] for i in range(N+1)]
for i in range(1,N+1,1):
    ruiseki_xor[i]=ruiseki_xor[i-1]^A[i]

#累積和
ruiseki = [0]*(N+1)
for i in range(1,N+1,1):
    ruiseki[i]=ruiseki[i-1]+A[i]

ans = 0
cersol = 1
for i in range(1,N+1,1):
    ans += max(cersol,i)-i
    for j in range(max(cersol,i),N+1,1):
        if ruiseki[j]-ruiseki[i-1] == ruiseki_xor[j]^ruiseki_xor[i-1]:
            ans += 1
        else:
            cersol = j-1
            break
        
        

print(ans)


### FIXED CODE ###

#累積xor
#累積和

N = int(input())
A = [0] + list(map(int,input().split()))

#累積xor
ruiseki_xor = [A[i] for i in range(N+1)]
for i in range(1,N+1,1):
    ruiseki_xor[i]=ruiseki_xor[i-1]^A[i]

#累積和
ruiseki = [0]*(N+1)
for i in range(1,N+1,1):
    ruiseki[i]=ruiseki[i-1]+A[i]

ans = 0
cersol = 1
for i in range(1,N+1,1):
    ans += cersol-i
    for j in range(cersol,N+1,1):
        if ruiseki[j]-ruiseki[i-1] == ruiseki_xor[j]^ruiseki_xor[i-1]:
            ans += 1
            cersol = j
        else:
            cersol = j
            break
        
        

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

import numpy as np
N, K = map(int, input().split())
A = list(map(lambda s: int(s)-1, input().split()))

n = 0
visit = [0]
for _ in range(K):
    n = A[n]
    if n not in visit:
        visit += [n]
    else:
        loop_start = visit.index(n)
        loop_length = len(visit) - loop_start
        print(visit[loop_start + ((K-loop_start) % loop_length)]+1)
        break
else:
    print(visit[-1]+1)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(lambda s: int(s)-1, input().split()))

n = 0
visit = {0}
ls = [0]
for _ in range(K):
    n = A[n]
    if n not in visit:
        visit.add(n)
        ls += [n]
    else:
        loop_start = 0
        loop_length = 0
        flag = False
        m = 0
        for _ in range(N):
            if n == m:
                if flag:
                    break
                else:
                    flag = True
            if flag:
                loop_length += 1
            else:
                loop_start += 1
            m = A[m]

        print(ls[loop_start + ((K-loop_start) % loop_length)]+1)
        break
else:
    print(n+1)
### BUGGY CODE ###

N = int(input())
List = [input() for i in range(N)]

c = [x for x in set(List) if List.count(x) > 1]
d = [x for x in set(List) if List.count(x) < 2]

print(len(c)+len(d))


### FIXED CODE ###

N = int(input())
List = [input() for i in range(N)]

print(len(set(List)))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
graph = [list() for _ in range(n**2)]

id_index = [[i+j*n for i in range(n)] for j in range(n)]
index_list = []

def toId(p, o):
    if p > o:
        index = id_index[o][p]
        index_list.append(index)
        return index
    else: return id_index[p][o]

v_len = [-1 for _ in range(n)] * n
finished = [False for _ in range(n)] * n

def dfs(id):
    next_list = graph[id]

    if v_len[id] != -1:
        if not finished[id]:
            print(-1)
            sys.exit()
        return v_len[id]

    v_len[id] = 1

    for next in next_list:
        v_len[id] = max(v_len[id], dfs(next)+1)

    finished[id] = True
    return v_len[id]

for p in range(n):
    a = [toId(p, int(x)-1) for x in input().split()]
    for i in range(n-2):
        graph[a[i]].append(a[i+1])
    
ans = 0

for id in index_list:
    ans = max(dfs(id), ans)

print(ans)

### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
graph = [list() for _ in range(n**2)]

id_index = [[i+j*n for i in range(n)] for j in range(n)]
index_list = []

def toId(p, o):
    if p > o:
        index = id_index[o][p]
        index_list.append(index)
        return index
    else: return id_index[p][o]

v_len = [-1 for _ in range(n)] * n
finished = [False for _ in range(n)] * n

def dfs(id):
    next_list = graph[id]

    if v_len[id] != -1:
        if not finished[id]:
            print(-1)
            sys.exit()
        return v_len[id]

    v_len[id] = 1

    for next in next_list:
        v_len[id] = max(v_len[id], dfs(next)+1)

    finished[id] = True
    return v_len[id]

for p in range(n):
    a = [toId(p, int(x)-1) for x in input().split()]
    for i in range(n-2):
        graph[a[i]].append(a[i+1])
    
ans = 0

for id in index_list:
    ans = max(dfs(id), ans)

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

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

for i in range(N):
    ans*=A[i]
    if A.count(0)>0:
        ans=0
        break
    if ans>10**18:
        ans=-1
        break
    

print(ans)

### FIXED CODE ###

import numpy as np
import math
import functools
import operator
N=int(input())
A = list(map(int, input().split()))
#AA=A.sort()
if A.count(0)>0:
    ans=0
elif N>30 and A.count(1)<10:
    ans=-1
    
else:
    ans=functools.reduce(operator.mul, A)
if ans>10**18 :
    ans=-1
print(ans)
### BUGGY CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rf = lambda: map(float, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
a = rl()
ans = 0
for li in itertools.combinations(a, 2):
    a, b = li
    ans = (ans + a*b)%mod
print(ans)












### FIXED CODE ###

import sys

ri = lambda: int(sys.stdin.readline())
rl = lambda: list(map(int, sys.stdin.readline().split()))
mod = 10**9 + 7

n = ri()
a = rl()
s = sum(a)
ans = 0
for i in a:
    s -= i
    ans = (ans + s*i)%mod
print(ans)
### BUGGY CODE ###

n=int(input())
ans=0
prea=0
pret=0
for i in range(n):
    
    i=0
    t,a=map(int,input().split())
    while 1:
        
        i+=1
        if ans<=(a+t)*i and a*i>=prea and t*i>=pret:
            ans=(a+t)*i
            prea,pret=a*i,t*i
            break
print(ans)

### FIXED CODE ###

from math import ceil
from decimal import *
n=int(input())
prea=Decimal("1.0")
pret=Decimal("1.0")
for i in range(n):
    
    t,a=map(Decimal,input().split())
    i=max(ceil(prea/a),ceil(pret/t))
    pret,prea=t*i,a*i

print(pret+prea)
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


sys.setrecursionlimit(2010)
print(dfs(0, n-1))


### FIXED CODE ###

import sys
import time

t = time.time()

n = int(input())
a = list(map(int, input().split(' ')))
b = list(range(n))
b.sort(key=lambda x: -a[x])
# print("b after:", b)
# print(list(map(lambda x:a[x],b)))
# print(time.time()-t)

cache = [[-1 for x in range(n)] for y in range(n)]
# print(cache)


def dfs(left, right):
    if left > right:
        return 0
    if cache[left][right] != -1:
        return cache[left][right]
    which = n-(right-left+1)
    ans1 = dfs(left+1, right)+abs(left-b[which])*a[b[which]]
    ans2 = dfs(left, right-1)+abs(right-b[which])*a[b[which]]
    cache[left][right] = max(ans1, ans2)
    return cache[left][right]


sys.setrecursionlimit(2010)
print(dfs(0, n-1))
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N)]
S_uni = set(S)
# print(S)
# print(S_uni)
m = 0
l = []
for i in S_uni:
    c = S.count(i)
    # print(i,c)
    if c > m:
        m = c
        l = [i]
    elif c == m:
        l.append(i)

# print("============")
l.sort()
for i in l:
    print(i)

### FIXED CODE ###

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

ini = S[0]
l = [0]
for i in range(N):
    if ini != S[i]:
        # print(ini,S[i])
        ini = S[i]
        l.append(i)
l.append(N)
l_sabun = [l[i+1] - l[i] for i in range(len(l)-1)]
# print(l)
# print(l_sabun )

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

# print(S_set)

m = max(l_sabun)
ans = [S_set[i] for i, x in enumerate(l_sabun) if x == m]

# print(m,ans)


# print("============")

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

#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur, cur - mn))

    tmp.sort(key=lambda x: (x[0], x[1]), reverse=True)
    #print(tmp)

    cur = 0
    idx = 0
    q = []
    count = 0
    while idx < N or len(q) > 0:
        while idx < N and cur + tmp[idx][0] >= 0:
            heapq.heappush(q, (-tmp[idx][2], -tmp[idx][1], -tmp[idx][0]))
            idx += 1
        if len(q) == 0:
            print(NO)
            return
        #print(count, q)
        diff, cnt, mn = heapq.heappop(q)
        diff, cnt, mn = -diff, -cnt, -mn
        #print(cnt, mn)
        if cur + mn < 0:
            print(NO)
            return
        cur += cnt
        count += 1

    #print(cur)
    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys, heapq
sys.setrecursionlimit(300000)

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(N: int, S: "List[str]"):
    tmp = []
    for i in range(N):
        cur = 0
        mn = 0
        for c in S[i]:
            if c == '(':
                cur += 1
            else:
                cur -= 1
                mn = min(mn, cur)
        tmp.append((mn, cur))

    tmp.sort(key=lambda x: (x[1] < 0, (-x[0] if x[1] >= 0 else -(x[1] - x[0]))))
    #tmp.sort(key=lambda x: (x[1] < 0, -x[0], x[1]))
    #print(tmp)

    cur = 0
    for mn, cnt in tmp:
        #print(cur, mn, cnt)
        if abs(mn) > cur:
            print(NO)
            return
        cur += cnt

    if cur == 0:
        ret = YES
    else:
        ret = NO
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, S)

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

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

cnt = [x]

for i in range(m+1):
    x = x*x % m
    if x in cnt:
        break
    cnt.append(x)

start = cnt.index(x)


ans = sum(cnt[:start])
roop = len(cnt) - start
#print(roop)
n = n-start
ans = ans + (n//roop)*sum(cnt[start:]) + sum(list(cnt)[start:(start+n%roop)])

print(ans)

### FIXED CODE ###

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

cnt = [x]
c = set()
c.add(x)

for i in range(m+1):
    x = x*x % m
    if x in c:
        break
    cnt.append(x)
    c.add(x)

start = cnt.index(x)

ans = sum(cnt[:start])
roop = len(cnt) - start

n = n-start
ans = ans + (n//roop)*sum(cnt[start:]) + sum(list(cnt)[start:(start+n%roop)])

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


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


    lst = []
    for i in a:
        lst.append(i)
        lst.append(i-1)
        lst.append(i+1)

    ans = -1
    for i in set(lst):
        ans = max(lst.count(i),ans)

    print(ans)



if __name__ == "__main__":
        main()


### FIXED CODE ###


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

    #lst = [0 for i in range(n*3)]
    ans_lst = [0 for i in range(max(a)+4)]
    """
    for i in range(n):
        lst[3*i] = a[i]
        lst[3*i+1] = a[i]+1
        lst[3*i+2] = a[i]+2
    """

    for i in a:
        ans_lst[i] += 1
        ans_lst[i+1] += 1
        ans_lst[i-1] += 1

    """
    ans = -1
    for i in set(lst):
        ans = max(lst.count(i),ans)
    """

    print(max(ans_lst))


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

import sys
n,w=map(int,sys.stdin.readline().split())
weight=[]
value=[]
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight.append(x)
    value.append(y)
l=len(weight)
dp=[[0]*(w+1) for j in range(l)]
for i in range(l):
    for w in range(total+1):
        if weight[i]<=w:
            dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[l-1][total])

### FIXED CODE ###

import numba as nb
import sys
import numpy as np
@nb.njit
def solve(w,weight,value):
    total=w
    dp = np.zeros(shape=(n + 1, w + 1), dtype=np.int64)
    for i in range(l):
        for w in range(total+1):
            if weight[i]<=w:
                dp[i][w]=max(value[i]+dp[i-1][w-weight[i]],dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    print(dp[l-1][total])
n,w=map(int,sys.stdin.readline().split())
weight=[0]*n
value=[0]*n
total=w
for i in range(n):
    x,y=map(int,sys.stdin.readline().split())
    weight[i]=x
    value[i]=y
l=len(weight)
solve(w,weight,value)