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

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    S = input()
    d = 1
    dp = [0] * 13
    dp[0] = 1
    dp_n = [None] * 13
    for s in reversed(S):
        for i in range(13):
            dp[i] %= N1097
            dp_n[i] = 0
        if s == '?':
            for s in range(10):
                diff = (s*d) % 13
                for i in range(13):
                    dp_n[(i+diff)%13] += dp[i]
        else:
            s = int(s)
            diff = (s*d) % 13
            for i in range(13):
                dp_n[(i+diff)%13] += dp[i]
        dp_n, dp = dp, dp_n
        d = (10 * d) % 13
    print(dp[5] % N1097)

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    S = input()
    d = 1
    dp = [0] * 13
    dp[0] = 1
    dp_n = [None] * 13
    for s in reversed(S):
        for i in range(13):
            dp[i] %= N1097
            dp_n[i] = 0
        if s == '?':
            for s in range(10):
                diff = (s*d) % 13
                for i in range(13):
                    dp_n[(i+diff)%13] += dp[i]
        else:
            s = int(s)
            diff = (s*d) % 13
            for i in range(13):
                dp_n[(i+diff)%13] += dp[i]
        dp_n, dp = dp, dp_n
        d = (10 * d) % 13
    print(dp[5] % N1097)

main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [0] * N
max_leng = 0

for i in range(0, N):
    leng = 0
    idx_i = i
    sta_j = -1

    j = i - 1
    while j > -1:
        if sta_j == idx_i:
            leng = 0
            idx_i = i
            j = sta_j-1
            sta_j = -1
            continue

        if S[idx_i] == S[j]:
            if leng == 0:
                sta_j = j
            leng += 1
            idx_i -= 1
            max_leng = max(leng, max_leng)
        else:
            j += leng
            leng = 0
            idx_i = i
        j -= 1
print(max_leng)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

dp = [[0] * N for i in range(N)]
max_leng2 = 0 
for i in range(0, N):
    leng2 = 0

    j = i - 1
    while j > -1:
        if S[i] == S[j]:
            sta_j = j
            if j != 0:
                leng2 = dp[i-1][sta_j-1] + 1
            else: 
                leng2 = 1
            
            if i - sta_j < leng2:
                leng2 = i - sta_j
                
            dp[i][sta_j] = leng2
            max_leng2 = max(max_leng2, leng2)
        j -= 1
print(max_leng2)
### BUGGY CODE ###

def expect(n):
    return (int(n)+1)/2
N, K = map(int,input().split()) 
P = list(map(expect,input().split()))
maxsize = sum(P[0:K])
for i in range(N-K):
    if P[i]>P[i+K]:
        pass
    else:
        if sum(P[i+1:i+K+1]) > maxsize:
            maxsize = sum(P[i+1:i+K+1])
print(maxsize)

### FIXED CODE ###

def expect(n):
    return (int(n)+1)/2
N, K = map(int,input().split()) 
P = list(map(expect,input().split()))
sumlist = [sum(P[0:K])]
sumnumber = sum(P[0:K])
for i in range(N-K):
    sumnumber -=P[i]
    sumnumber +=P[i+K]
    sumlist.append(sumnumber)
print(max(sumlist))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [a.index(i+1)+1 for i in range(n)]
ans = ''
for i in b:
    ans += str(i) + ' '
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [[a[i], i+1] for i in range(n)]
b.sort()
c = [b[i][1] for i in range(n)]
print(*c)
### BUGGY CODE ###

s = input()
n = int(input())

for i in range(n):
    a = input()
    if a == "1":
        s = s[::-1]
    else:
        b,c,d = a.split()
        if c == "1":
            s = d + s
        else:
            s = s + d

print(s)



### FIXED CODE ###

from collections import deque

s = deque(list(input()))
n = int(input())
f = True

for i in range(n):
    a = input()
    if a == "1":
        f = not f
    else:
        b,c,d = a.split()
        if f:
            if c == "1":
                s.appendleft(d)
            else:
                s.append(d)
        else:
            if c == "1":
                s.append(d)
            else:
                s.appendleft(d)

if not f:
    s.reverse()

ans = "".join(s)
print(ans)
### BUGGY CODE ###

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

a_ = []
for i,v in enumerate(a):
    a_.append([i+1,v])
a_.sort(key = lambda x: x[1], reverse=True)

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    DP[0][i] = DP[0][i-1] + abs(a_[i-1][1] * (n - i + 1 - a_[i-1][0]))
    DP[i][0] = DP[i-1][0] + abs(a_[i-1][1] * (a_[i-1][0] - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(a_[i-1][1] * (a_[i-1][0] - x)),  \
            DP[x][y-1] + abs(a_[i-1][1] * (n - y + 1 - a_[i-1][0])))

ans = 0
for i in range(n+1):
    ans = max(ans, DP[i][n-i])

print(ans) 

### FIXED CODE ###

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

a = list(enumerate(a))
a.sort(key = lambda x: x[1])

DP = [[0 for i in range(n+1)] for j in range(n+1)]
DP[0][0] = 0
for i in range(1, n+1):
    pos, val = a.pop()
    pos = pos + 1

    DP[0][i] = DP[0][i-1] + abs(val * (n - i + 1 - pos))
    DP[i][0] = DP[i-1][0] + abs(val * (pos - i))
    for x in range(1, i):
        y = i - x
        DP[x][y] = max(DP[x-1][y] + abs(val * (pos - x)),  \
            DP[x][y-1] + abs(val * (n - y + 1 - pos)))

ans = 0
for i in range(n+1):
    ans = max(ans, DP[i][n-i])

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

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

def dist(x1, y1, x2, y2):
    return (x1-x2) ** 2 + (y1-y2) ** 2

import heapq
seen = set()
queue = [(0, dist(CH-1, CW-1, DH-1, DW-1), CH-1, CW-1)]



while queue:
    move, _, row, col = heapq.heappop(queue)

    if (row, col) in seen:
        continue
    # print(row, col, S[row][col], move, queue)
    if row == DH-1 and col == DW-1:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            heapq.heappush(queue, (move, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                heapq.heappush(queue, (move+1, dist(new_row, new_col, DH-1, DW-1), new_row, new_col))

print(-1)


### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))

# 1-index -> 0-index
CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    # print(row, col, queue)

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)
### BUGGY CODE ###

N, K = map(int, input().split())
ans = 10**10
while True:
    temp = N % K
    if temp < ans:
        ans = temp
    elif temp == ans:
        break

ans = min(abs(ans-K), ans)
print(ans)


### FIXED CODE ###

# C
N, K = map(int, input().split())
ans = 10**10
mod = N % K
ans = min(mod, abs(mod-K))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from fractions import gcd

N=int(input())
a_list = list(int(i) for i in input().split())
MOD = 10**9+7


def cal_lcm(a, b):
  return int(a*b//gcd(a,b))


lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = ans*(lcm_//lcm)  % MOD
  ans = (ans + (lcm_//a_list[i])) % MOD
  lcm = lcm_

print(ans)

### FIXED CODE ###

from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += lcm//a_list[i]
print(ans%MOD)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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


lcm=[0]*(10**6+5)





for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for j in range(2,len(lcm)):
    l*=pow(j,lcm[j])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    ans%=mod
    
print(ans%mod)




### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

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


for i in range(N):
    a=A[i]
    for j in range(2,a):
        temp=0
        while a%j==0:
            a=a//j
            temp+=1
        lcm[j]=max(lcm[j],temp)
        if a==1 or j*j>A[i]:
            break
    if a!=1:
        lcm[a]=max(lcm[a],1)
                
        
l=1
for d in lcm.items():
    l*=pow(d[0],d[1])
    

ans=0
mod=10**9+7

for i in range(N):
    ans+=l//A[i]
    
print(ans%mod)
### BUGGY CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n,m =na()
ls = [i for i in range(1,n+1)]
for i in range(m):
    l, r = na()
    tmp = [j for j in range(l, r+1)]
    ls = list(set(ls) & set(tmp))

print(len(ls))


### FIXED CODE ###

import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n,m =na()
ls = 1
rs = n
for i in range(m):
    l, r = na()
    ls = max(ls, l)
    rs = min(rs, r)
if ls > rs:
    print(0)
else:
    print(rs - ls + 1)
### BUGGY CODE ###

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    INF = 10 ** 9
    dp = [INF] * (N+1)
    dp[0] = 0
    
    for i in range(1, N):
        for j in range(K, 0, -1):
            if i-j < 0: continue
            dp[i] = min(dp[i], dp[i-j] + abs(A[i] - A[i-j]))

    return dp[N-1]

print(solve())

### FIXED CODE ###

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    INF = 10 ** 9
    dp = [INF] * (N+1)
    dp[0] = 0
    
    for i in range(1, N):
        for j in range(K, 0, -1):
            if i-j < 0: continue
            dp[i] = min(dp[i], dp[i-j] + abs(A[i] - A[i-j]))

    return dp[N-1]

print(solve())
### BUGGY CODE ###

from scipy.special import perm
from scipy.special import comb

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

p = perm(m,n,exact=True)

d = [0]*n
d[0] += p
for i in range(1,n):
  d[i] += (perm(m,n-i,exact=True)*(perm(m-n+i,i,exact=True)**2) - sum(d[:i]))*comb(n,i,exact=True)

ans = (p**2 - sum(d[:n])) % (10**9 + 7)
print(ans)

### FIXED CODE ###

def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs
        

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

MOD = 10 ** 9 + 7
modFacts, invs = prepare(max(N, M))

ans = 0
for i in range(N + 1):
    Ti = (modFacts[N] * invs[i] * invs[N - i]) % MOD
    Ti *= (modFacts[M] * invs[M - i]) % MOD
    Ti %= MOD
    Ti *= pow(modFacts[M - i] * invs[(M - i) - (N - i)], 2, MOD)
    Ti %= MOD
    ans += pow(-1, i) * Ti
    ans %= MOD

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

N=int(input())
A=[int(input()) for i in range(N)]
lst=[]
nowN=max(A)+1
i=0
while i<N:
    if nowN>=A[i]:
        nowN=A[i]
        lst.append([A[i]])
    else:
        lst2=[n[-1] for n in lst]
        flag=0
        for n in range(len(lst2)):
            if lst2[n]<A[i]:
                lst[n].append(A[i])
                flag=1
                break
        if not flag:
            lst.append([A[i]])
    i+=1
print(len(lst))


### FIXED CODE ###

import bisect
import collections

N=int(input())
A=[int(input()) for i in range(N)]
B=[0 for i in range(N)]
C=sorted(A)
count=0
lst=collections.deque([])
for i in range(N):
    if A[i]==C[-1]:
        C.pop()
        if lst:
            lst.pop()
        else:
            count+=1
        continue
    idx=bisect.bisect_left(lst,A[i])-1
    #print(idx,lst,A[i])
    if idx<0:
        lst.appendleft(A[i])
        count+=1
    else:
        lst[idx]=A[i]

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

import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)
        double = bisect_left(A, h - a)
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        for k in range(j, min(N - 1, double + 1)):
            heapq.heappush(Q, a + A[k])

    if count > M:
        for _ in range(count - M):
            minus = heapq.heappop(Q)
            total -= minus

    print(total)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from bisect import bisect, bisect_left
import heapq

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    S = [0] * (N + 1)
    for i, a in enumerate(A): S[i + 1] = a + S[i]
 
    l, h = 1, A[N-1] * 2 + 1
    while h - l > 1: #最小値がｍ以上の要素をM個用意できるか
        m = (h + l) // 2
        count = 0
        for i, a in enumerate(A): count += N - bisect_left(A, m - a)
        if count >= M: 
            l = m
        else: h = m

    total = 0
    count = 0
    Q = []
    heapq.heapify(Q)
    min_out = 10000000
    for i, a in enumerate(A):
        j = bisect_left(A, l - a)  
        total += a * (N - j) + (S[N] - S[j])
        count += N - j
        if 0 <= j < N: min_out = min(min_out, a + A[j])

    if count > M:
        total -= min_out * (count - M)

    print(total)

    return 0

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

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

n=[1]
t=1

while True:
  t=A[t-1]
  if t in n:
    f=n.index(t)
    break
  n.append(t)

k=len(n)-f

if K>=f:
  print(n[f+(K-f)%k])

else:
  print(n[K])
  


### FIXED CODE ###

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

n=[1]
t=1
ord=[-1]*(N+1)
ord[0]=0

while True:
    t=A[t-1]
    if ord[t] != -1:
        f=n.index(t)
        break
    n.append(t)
    ord[t]=0

k=len(n)-f

if K>=f:
    print(n[f+(K-f)%k])

else:
    print(n[K])
### BUGGY CODE ###

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

counter = 1
for i in range(1,n):
    if all( x>= P[i] for x in  P[0:i] ):

        counter +=1

print(counter)

### FIXED CODE ###

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

minimum = float('inf')
ans = 0
for p in P:
    if p <=minimum:
        minimum = p
        ans += 1
print(ans)
### BUGGY CODE ###

p = [True] * 100000
for x in xrange(2, int(100000 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100000):
            if y * x >= 100000:
                break
            p[x * y] = False
p[0], p[1] = False, False
e = []
for i in xrange(100000):
    s = False
    if p[i] and p[(i + 1) / 2]:
        s = True
    e.append(s)
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print sum(e[l: r + 1])


### FIXED CODE ###

p = [True] * 100020
for x in xrange(2, int(100020 ** 0.5) + 1):
    if p[x]:
        for y in xrange(2, 100020):
            if y * x >= 100020:
                break
            p[x * y] = False
p[0], p[1] = False, False
e, s = [], 0
for i in xrange(100020):
    e.append(s)
    if p[i] and p[(i + 1) / 2]:
        s += 1
for _ in xrange(input()):
    (l, r), c = map(int, raw_input().split()), 0
    print e[r + 1] - e[l]
### BUGGY CODE ###

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

l=[]
for i in range(n-k+1):
    total=1
    for j in range(0+i,k+i):
        total*=a[j]
    l.append(total)

for i in range(n-k):
    if l[i]<l[i+1]:
        print('Yes')
    else:
        print('No')  

### FIXED CODE ###

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

for i in range(n-k):
    if a[i]<a[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

from collections import defaultdict

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


def combi(n):
    return n * (n-1) // 2


for a in A:
    d[a] += 1

for i in range(N):
    ans = []
    tmp = d.copy()
    tmp[A[i]] -= 1
    tmp = list(tmp.values())
    for t in tmp:
        if memo[t] == 0:
            memo[t] = combi(t)
        ans.append(memo[t])
    print(sum(ans))

### FIXED CODE ###

from collections import defaultdict


def combi(n):
    if n < 2:
        return 0
    return n * (n-1) // 2


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

for a in A:
    d[a] += 1

whole = sum(list(map(combi, list(d.values()))))

diff = []
for i in range(N):
    diff.append(combi(d[A[i]]) - combi(d[A[i]] - 1))

for x in diff:
    print(whole - x)
### BUGGY CODE ###

import sys

n, m = input().split()
i = [input() for i in range(int(m))]

n_l = [0] * int(n)
w_l = [0] * int(n)
p_l = []

a = 0
w = 0
for i_s in i:
    p, c = i_s.split()
    p = int(p) - 1
    if n_l[p] == 1:
        continue

    if p not in p_l:
        p_l.append(p)

    if c == "AC":
        n_l[p] = 1
    else:
        w_l[p] += 1

for p in p_l:
    if n_l[p] == 1:
        a += 1
        w += w_l[p]

print("{} {}".format(a, w))


### FIXED CODE ###

import sys
import numpy as np

n, m = input().split()
i = [input() for i in range(int(m))]

n_l = [False] * int(n)
w_l = [0] * int(n)

for i_s in i:
    p, c = i_s.split()
    p = int(p) - 1
    if n_l[p] == 1:
        continue

    if c == "AC":
        n_l[p] = True
    else:
        w_l[p] += 1

n_l = np.array(n_l)
w_l = np.array(w_l)
w_l = w_l[n_l]

print("{} {}".format(n_l.sum(), w_l.sum()))
### BUGGY CODE ###

ai = lambda: list(map(int,input().split()))

n = int(input())
a = ai()

ans = 0
for i in range(n):
    s = 0
    for j in range(i,n):
        if s+a[j] == s^a[j]:
            ans += 1
            s += a[j]
        else:
            break
print(ans)

### FIXED CODE ###

ai = lambda: list(map(int, input().split()))

n = int(input())
a = ai()

ans = 0
start = 0
s = 0
for i in range(n):
    for j in range(start, n):
        if s + a[j] == s ^ a[j]:
            s += a[j]
        else:
            s -= a[i]
            start = j
            ans += j-i
            break
        if j == n-1:
            for k in range(i,n):
                ans += n-k
            print(ans)
            import sys
            sys.exit()
print(ans)
### BUGGY CODE ###

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

for i in A:
  c = 0
  for j in A:
    if(j == i):
      c += 1
    if(c > 1):
      print("NO")
      exit()
print("YES")

### FIXED CODE ###

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

if (len(A) == len(set(A))):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    # See:
    # https://atcoder.jp/img/arc078/editorial.pdf
    total_a = sum(a)
    diff = float('inf')

    for i in range(1, n):
        diff = min(diff, abs(total_a - 2 * sum(a[:i])))

    print(diff)


### FIXED CODE ###

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

# AtCoder Beginner Contest
# Problem C

if __name__ == '__main__':
    from itertools import accumulate

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

    # See:
    # https://atcoder.jp/img/arc078/editorial.pdf
    # total_a = sum(a)
    summed_a = [0] + list(accumulate(a))
    total_a = sum(a)
    diff = float('inf')

    for i in range(1, n):
        diff = min(diff, abs(total_a - 2 * summed_a[i]))

    print(diff)
### BUGGY CODE ###

N=int(input())
S=input()
# N=int(Input[0][0])
# S=Input[1][0]
count=0
for i in range(1,N-1):
    for j in range(i+1,N):
        for k in range(j+1,N+1):
            if S[i-1]!=S[j-1] and S[i-1]!=S[k-1] and S[j-1]!=S[k-1] and j-i!=k-j:
                    count+=1
print(count)  

### FIXED CODE ###

N=int(input())
S=input()
# N=int(Input[0][0])
# S=Input[1][0]
import math
count=0
counter={'R':0,'G':0,'B':0}
for i in S:
    counter[i]+=1
s=counter['R']*counter['G']*counter['B']
for i in range(1,N-1):
    for j in range(i+1,N):
        k=2*j-i
        if k<=N and (S[i-1]!=S[j-1] and S[i-1]!=S[k-1] and S[j-1]!=S[k-1]):
                count+=1
print(s-count)
### BUGGY CODE ###

import math
k = int(input())
sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += math.gcd(math.gcd(a, b), c)
print(sum)


### FIXED CODE ###

import math
k = int(input())
sum = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            sum += math.gcd(math.gcd(a, b), c)
print(sum)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(n-1):
  if i+1 not in a:
    b[i+1]+=b[i]
  if i+2 not in a:
    b[i+2]+=b[i]

if n not in a:
  b[n]+=b[n-1]

print(b[n]%(10**9+7))


### FIXED CODE ###

n,m=map(int,input().split())
a=[]
a = set(int(input()) for _ in range(m))
#for i in range(m):
#  a.append(int(input()))
b=[0 for x in range(n+1)]
b[0]=1
for i in range(1,n+1):
  if i in a:
    continue
  x=b[i-1]
  if i>1:x+=b[i-2]
  b[i]=x
print(b[n]%(10**9+7))