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

A, B = list(int(el) for el in input().split(' '))

set_a=set()
set_b=set()

set_a.add(1)
set_b.add(1)

num=2

while True:
  if A%num == 0:
    A=A//num
    if num not in set_a: set_a.add(num)
  else:
    num+=1
    
  if num >= A+1: break
    
num=2
while True:
  if B%num == 0:
    B=B//num
    if num not in set_b: set_b.add(num)
  else:
    num+=1
    
  if num >= B+1: break

print(len(set_a & set_b))

### FIXED CODE ###

A, B = list(int(el) for el in input().split(' '))


if (A==1) or (B==1): 
  print(1) 
  is_print=False
else:
  def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
      if temp%i==0:
        cnt=0
        while temp%i==0:
          cnt+=1
          temp //= i
        arr.append([i, cnt])

    if temp!=1:
      arr.append([temp, 1])

    if arr==[]:
      arr.append([n, 1])

    return arr

  fact_a = factorization(A)
  fact_b = factorization(B)

  set_a = set()
  set_b = set()

  set_a.add(1)
  set_b.add(1)

  for fa, _ in fact_a: set_a.add(fa)
  for fb, _ in fact_b: set_b.add(fb)


  print(len(set_a & set_b))
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
			

print(N - len(need))


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
### BUGGY CODE ###

from math import hypot,atan2,pi,cos
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]

K = 500000
ans = 0
for i in range(K+1):
    t1 = 2*pi*i/K - pi
    r = 0
    for x,y in XY:
        t2 = atan2(y,x)
        a,b = (t1,t2) if t1<t2 else (t2,t1)
        if b-a > 3*pi/2:
            a += 2*pi
            a,b = b,a
        d = hypot(x,y) * cos(b-a)
        if d > 0:
            r += d
    ans = max(ans, r)
print(ans)

### FIXED CODE ###

from math import hypot,atan2
N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N)]
xy = sorted(XY, key=lambda x:atan2(x[1],x[0]))
xy += xy

ans = 0
for i in range(N):
    sx = sy = 0
    for j in range(N):
        x,y = xy[i+j]
        sx += x
        sy += y
        d = hypot(sx,sy)
        if d > ans:
            ans = d
print(ans)
### BUGGY CODE ###

N = int(input())
p = 1
for i in range(1,N+1):
    p *= i
print(p % 1000000007)

### FIXED CODE ###

import math
N = int(input())
p = math.factorial(N)
print(p % 1000000007)
### BUGGY CODE ###

k = int(input())
x = 7%k

flg = True
for i in range(1,10**12):
  x = x%k
  if x ==0:
    break
  else:
    x = x*10+7
    
if k%2==0:
  flg = False
    
print(i if flg else '-1')


### FIXED CODE ###

k = int(input())
x = 7%k

flg = False
for i in range(1,k+1):
  x = x%k
  if x ==0:
    flg = True
    break
  else:
    x = x*10+7
  
print(i if flg else '-1')
### BUGGY CODE ###

INF=float('inf')
n,m=map(int,input().split())
a=[0]*m
c=[0]*m
for i in range(m):
    a[i],_=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))
dp=[INF]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            dp[j]=min(dp[j],a[i])
        dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(-1 if dp[-1]==INF else dp[-1])

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
for i in range(m):
    a[i],b[i]=map(int,input().split())
    c[i]=sum(map(lambda x:2**(int(x)-1),input().split()))

dp=[-1]*(2**n)
for i in range(m):
    for j in range(2**n):
        if j|c[i]==c[i]:
            if dp[j]<0:
                dp[j]=a[i]
            else:
                dp[j]=min(dp[j],a[i])
for i in range(m):
    for j in range(2**n):
        if dp[j]<0:
            continue
        if dp[c[i]|j]<0:
            dp[c[i]|j]=dp[j]+a[i]
        else:
            dp[c[i]|j]=min(dp[c[i]|j],dp[j]+a[i])
print(dp[-1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
from collections import deque
import bisect
x,y,z=[],[],[]
for i in range(3*N):
    if 0<=i<N:x.append(A[i])
    elif N<=i<2*N:y.append(A[i])
    elif 2*N<=i<3*N:z.append(A[i])
a=x+y
a.sort()
mae=[sum(a[N:2*N])]
for i in range(N-1,-1,-1):
    idx=bisect.bisect_left(a,y[i])
    if y[i]>a[-1*N-1]:
        mae.append(mae[-1]-a[idx]+a[-1*N-1])
        a.pop(idx)
    else:
        mae.append(mae[-1])
        a.pop(idx)
b=y+z
b.sort()
ushiro=[-1*sum(b[0:N])]
for i in range(N):
    idx=bisect.bisect_left(b,y[i])
    if y[i]<b[N]:
        ushiro.append(ushiro[-1]+b[idx]-b[N])
        b.pop(idx)
    else:
        ushiro.append(ushiro[-1])
        b.pop(idx)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)

### FIXED CODE ###

from heapq import heappush,heappop
dataX=[]
dataY=[]
mae=dict()
ushiro=dict()
N=int(input())
A=list(map(int,input().split()))
X=A[0:N]
Y=A[N:2*N]
Z=A[2*N:3*N]
for i in range(N):
    heappush(dataX,X[i])
    heappush(dataY,-1*Z[i])
mae[0]=sum(X)
ushiro[0]=-1*sum(Z)
for i in range(1,N+1):
    mae[i]=mae[i-1]+Y[i-1]
    heappush(dataX,Y[i-1])
    mae[i]-=heappop(dataX)
    ushiro[i]=ushiro[i-1]-Y[N-i]
    heappush(dataY,-1*Y[N-i])
    ushiro[i]-=heappop(dataY)
ans=-1*float('inf')
for i in range(N+1):
    ans=max(ans,mae[i]+ushiro[N-i])
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    K = int(input())
    ranks = ["~"] * K
    for l in range(len(s)):
        for r in range(l+1, len(s)+1):
            target = s[l:r]
            if target in ranks:
                continue
            if target < ranks[K-1]:
                ranks[K-1] = target
            for i in range(K-1, 0, -1):
                if ranks[i] < ranks[i-1]:
                    tmp = ranks[i]
                    ranks[i] = ranks[i-1]
                    ranks[i-1] = tmp
    print(ranks[K-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    s = input()
    K = int(input())
    ranks = ["~"] * K
    for l in range(len(s)):
        for r in range(l+1, min(len(s)+1, l+6)):
            target = s[l:r]
            if target in ranks:
                continue
            if target < ranks[K-1]:
                ranks[K-1] = target
            for i in range(K-1, 0, -1):
                if ranks[i] < ranks[i-1]:
                    tmp = ranks[i]
                    ranks[i] = ranks[i-1]
                    ranks[i-1] = tmp
    print(ranks[K-1])


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

N = int(input())
l = input().split()
H = []
for i in range(N):
  H.append(int(l[i]))
r = 0
for i in range(N):
  for j in range(i, N):
    if i > j and i - j == H[i] + H[j]:
      r += 1
    elif j > i and j - i == H[i] + H[j]:
      r += 1
print(r)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N = int(readline())
  line = readline().split()
  R = {}
  L = {}
  for i in range(N):
    r = int(line[i]) + i + 1
    l = i + 1 - int(line[i])
    if r in R:
      R[r] += 1
    else:
      R[r] = 1
    if l in L:
      L[l] += 1
    else:
      L[l] = 1
  cnt = 0
  for i in R:
    if i in L:
      cnt += R[i] * L[i]
  print(cnt)
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

from collections import deque


def bfs(q):
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1


H, W = map(int, input().split())
field = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            dist[i][j] = 0
            q.append((i, j))
bfs(q)
print(max(v for row in dist for v in row))


### FIXED CODE ###

from collections import deque


def bfs(q):
    ans = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and dist[ni][nj] < 0:
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
                ans = max(ans, dist[ni][nj])
    return ans


H, W = map(int, input().split())
field = [input() for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == "#":
            dist[i][j] = 0
            q.append((i, j))
print(bfs(q))
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N)]

for i in range(0, N):
    wi, vi = map(int, input().split())
    for w in range(1, W+1):
        if w >= wi:
            dp[i][w] = max(dp[i-1][w - wi] + vi, dp[i-1][w])
        else:
            dp[i][w] = dp[i-1][w]
print(dp[N-1][W])

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline

N, W = map(int, input().split())
dp = np.zeros((N, W+1), dtype='int64')

def solve(N, W):
    for i in range(0, N):
        wi, vi = map(int, input().split())
        dp[i][:wi] = dp[i-1][:wi]
        dp[i][wi:] = np.fmax(dp[i-1][wi:],
                            dp[i-1][:W+1-wi] + vi)
    return dp[N-1][W]

print(solve(N, W))
### BUGGY CODE ###

s = list(input())
ans = 0
ls = len(s)
i = 0
while i < ls-2:
    if s[i:i+3] == ['A', 'B', 'C']:
        ans += 1
        s[i:i+3] = ['B', 'C', 'A']
        i -= 1
        continue
    i += 1
print(ans)


### FIXED CODE ###

s = list(input())
ans = 0
ls = len(s)
i = 0
ca = 0
while i < ls-2:
    if s[i:i+3] == ['A', 'B', 'C']:
        ans += 1 + ca
        # print(i, ans, ca)
        s[i+2] = 'A'
        if ca >= 1:
            ca -= 2
            s[i+1] = 'A'
        else:
            ca = 0
        continue
    elif s[i] == 'A':
        ca += 1
    else:
        ca = 0
    i += 1

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

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a = sorted(a)
    ops = sorted(ops, reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        for i, a_i in enumerate(a[start:start+count+1]):
            if a_i < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[start+i] = ope
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, m, a, ops):
    a.sort()
    ops.sort(reverse=True)
    # pprint(a)
    # pprint(ops)
    start = 0
    for ope, count in ops:
        i = 0
        for a_i in xrange(start, start+count):
            if a_i >= n:
                break
            if a[a_i] < ope and count > 0:
                count -= 1
                # print a_i, '=>', ope, ' count:', count
                a[a_i] = ope
                i += 1
            else:
                break
        start += i

    print sum(a)

if __name__ == '__main__':

    ops = []
    n, m = map(int, sys.stdin.readline().strip().split(" "))
    a = map(int, sys.stdin.readline().strip().split(" "))
    for _ in range(m):
        b, c = map(int, sys.stdin.readline().strip().split(" "))
        ops.append((c, b))

    solve(n, m, a, ops)
### BUGGY CODE ###

k = int(input())

ans = 0
def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += gcd(gcd(i,j),s)

print(ans)

### FIXED CODE ###

k = int(input())

ans = 0
def gcd(x,y):
    while y:
        x, y = y, x % y
    return x

for i in range(1,k+1):
    for j in range(1,k+1):
        for s in range(1,k+1):
            ans += gcd(gcd(i,j),s)

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

import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import random
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, N = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

# dp[h]: 体力を h にするのに必要な魔力の合計の最小値
dp = [INF] * (H + 1)
dp[H] = 0
for a, b in AB:
    for h in reversed(range(H + 1)):
        dp[max(0, h - a)] = min(dp[h] + b, dp[max(0, h - a)])
print(dp[0])


### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

H, N = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

# dp[h]: 体力を h にするのに必要な魔力の合計の最小値
dp = [INF] * (H + 1)
dp[H] = 0
for a, b in AB:
    for h in reversed(range(H + 1)):
        dp[max(0, h - a)] = min(dp[h] + b, dp[max(0, h - a)])
print(dp[0])
### BUGGY CODE ###

n, k, q = map(int, input().split())
arr = [k for _ in range(n)]

for _ in range(q):
    winner_id = int(input()) - 1
    arr = [ele - 1 for ele in arr]
    arr[winner_id] += 1

for ele in arr:
    if ele > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

n, k, q = map(int, input().split())
arr = [k - q] * n

for _ in range(q):
    winner_id = int(input()) - 1
    arr[winner_id] += 1

for ele in arr:
    if ele > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,m = map(int,input().split()) #nがカードの数、mがBの数
a = list(map(int, input().split()))
b = [list(map(int,input().split())) for i in range(m)]
 
for i in range(m):
  a.extend([b[i][1]]*b[i][0])
a.sort(reverse=True)
ans = 0
for i in range(n):
  ans += a[i]
print(ans)

### FIXED CODE ###

import numpy as np

n,m = map(int,input().split()) #nがカードの数、mがBの数
a = list(map(int, input().split())) #数のカウント
b = [1 for i in range(n)] #枚数カウント

for i in range(m):
  x, y = map(int, input().split())
  b.append(x)
  a.append(y)
c = np.array(a) #カードの数字
d = np.array(b) #カードの枚数
e = np.argsort(-c) #インデックスをカードの数字の大きい順にソート
#print(c,d,e)
ans = 0
N = 0 #取った枚数のカウント
i = 0
while N < n:
  j = e[i]
  if N + d[j] <= n:
    ans += c[j]*d[j]
    N += d[j]
    i += 1
  else:
    ans += c[j]*(n-N)
    N = n
    i += 1
print(ans)
### BUGGY CODE ###

# D - Lamp

H, W = map(int, input().split())
M = [[str(m) for m in input()] for _ in range(H)]
U = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if M[i][j] != '#':
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i - 1][j] + 1
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j - 1] + 1

        if M[H - i - 1][W - j - 1] != '#':
            if i == 0:
                D[H - i - 1][W - j - 1] = 1
            else:
                D[H - i - 1][W - j - 1] = D[H - i][W - j - 1] + 1
            if j == 0:
                R[H - i - 1][W - j - 1] = 1
            else:
                R[H - i - 1][W - j - 1] = R[H - i - 1][W - j] + 1

ans = 0
for i in range(H):
    for j in range(W):
        p = U[i][j] + L[i][j] + D[i][j] + R[i][j] - 3
        ans = max(ans, p)

print(ans)


### FIXED CODE ###

# # D - Lamp

import numpy as np

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
M = (np.array(M) == '.') * 1

L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)

for i in range(W):
    if i == 0:
        L[:, i] = M[:, i]
        R[:, W - i - 1] = M[:, W - i - 1]
    else:
        L[:, i] = (L[:, i - 1] + 1) * M[:, i]
        R[:, W - i - 1] = (R[:, W - i] + 1) * M[:, W - i - 1]

for i in range(H):
    if i == 0:
        U[i, :] = M[i, :]
        D[H - i - 1, :] = M[H - i - 1, :]
    else:
        U[i, :] = (U[i - 1, :] + 1) * M[i, :]
        D[H - i - 1, :] = (D[H - i, :] + 1) * M[H - i - 1, :]

print(max(np.max(L + R + D + U - 3), 0))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

count = 0
for i in range(N // R + 1):
    tmp = N - i * R
    for j in range(N // G + 1):
        tmp2 = tmp - j * G
        if tmp2 < 0:
            continue
        if tmp2 % B == 0:
            count += 1

print(count)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

count = 0
tmp1 = N + R
for i in range(N // R + 1):
    tmp1 -= R
    tmp2 = tmp1 + G
    for j in range(N // G + 1):
        tmp2 -= G
        if tmp2 < 0:
            continue
        if tmp2 % B == 0:
            count += 1

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

x = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


for number in factorization(x):
  for a in range(number[0]**5):
    b = a - number[0]
    if a**5 - b**5 == x:
      print(a,b)
      break
    elif a**5 - (-b)**5==x:
      print(a,-b)
      break

### FIXED CODE ###

import sys
x = int(input())

for a in range(120):
  for b in range(120):
    if a**5 - b**5 == x:
      print(a,b)
      sys.exit()
    elif a**5 - (-b)**5==x:
      print(a,-b)
      sys.exit()
### BUGGY CODE ###

S=input()
T=input()
ans = 1
for i in range(len(S)):
    if S.count(S[i]) != T.count(T[i]):
        ans = 0
        break
print("Yes" if ans == 1 else "No")

### FIXED CODE ###

s=input()
t=input()
dict_s = {}
dict_t = {}
ans = 0

for i in range(len(s)):
    s1 = s[i]
    if s1 in dict_s.keys():
        dict_s[s1] += 1
    else:
        dict_s[s1] = 1

for i in range(len(t)):
    t1 = t[i]
    if t1 in dict_t.keys():
        dict_t[t1] += 1
    else:
        dict_t[t1] = 1

for i in range(len(s)):
    if dict_s[s[i]] != dict_t[t[i]]:
        ans = 1
        break

print("Yes" if ans==0 else "No")
### BUGGY CODE ###

n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = [[0]*n for i in range(n)]
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            a,b = sorted([cur,next_i])
            col = (col+1)%k
            c[a][b] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[a][b]+1)


### FIXED CODE ###

n = int(input())
ab = []
g = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
    ab.append([a,b])

k = max([len(i) for i in g])
print(k)

reach = [False]*n
c = dict()
from collections import deque
q = deque([[0,-1]])

while q:
    cur,col = q.popleft()
    reach[cur] = True
    for next_i in g[cur]:
        if not reach[next_i]:
            col = (col+1)%k
            a,b = sorted([cur,next_i])
            c[(a,b)] = col
            q.append([next_i,col])

for a,b in ab:
    print(c[(a,b)]+1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for i in range(60):
  n = sum([x%2 for x in A])
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  if all(x==0 for x in A):
    break
print(res%(7+10**9))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N=int(input().rstrip('\n'))
A=[int(x) for x in input().rstrip('\n').split()]
res = 0
t=1
for _ in range(60):
  n = sum(x%2 for x in A)
  A = [x//2 for x in A]
  res += n*(N-n)*t
  t = t*2
  res = res%(7+10**9)
  if all(x==0 for x in A):
    break
print(res)
### BUGGY CODE ###

N = int(input())
c = list(input())

while True:
    if len(c) >= 1 and c[0] == 'R':
        del c[0]
    else:
        N = len(c)
        break

if N <= 1:
    print(0)
else:
    ans = 0
    r = N
    for w in range(N):
        if c[w] == 'R':
            continue
        else:
            while True:
                r += -1
                if r == -1 or c[r] == 'R':
                    break
            if r < w:
                break
            else:
                ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())
c = list(input())

if N <= 1:
    print(0)
else:
    ans = 0
    r = N
    for w in range(N):
        if c[w] == 'R':
            continue
        else:
            while True:
                r += -1
                if r == -1 or c[r] == 'R':
                    break
            if r < w:
                break
            else:
                ans += 1
    print(ans)
### BUGGY CODE ###

n=input()
p=[]
q=[0]*n
ans=0
for i in range(n):
    p.append(input())
for i in range(n-1,-1,-1):
    if p[i]>q[i]:
        if p[i]>i:
            print -1
            break
        for j in range(i-p[i]+1,i+1):
            q[j]=q[j-1]+1
            ans+=1
    elif p[i]<q[i]:
        print -1
        break
else:
    print ans


### FIXED CODE ###

n=input()
last=-1
#q=[0]*n
now=0
ans=-1
for i in range(n):
    now=input()
    if now>i or now-last>1:
        print -1
        break
    if now==last+1:
        ans+=1
    elif now<=last:
        ans+=now
    last=now
else:
    print ans