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

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

if n >= 40 or p == 1:
    print("1")
else:
    s = 0
    fact = []
    while s == 0:
        for i in range(2,p+1):
            if p%i == 0:
                p = p//i
                if p == 1:
                    s = 1
                fact.append(i)
                break
    c = collections.Counter(fact)
    ans = 1
    for i in c:
        if c[i] >= n:
            ans = ans*i**(c[i]//n)
    print(ans)

### FIXED CODE ###

import time

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

if n >= 40 or p == 1:
    print("1")
elif n == 1:
    print(p)
else:
    s = 0
    fact = {}
    start = time.time()
    check = False
    while s == 0:
        for i in range(2,p+1):
            now = time.time()
            if now > start+1.9:
                s = 1
                check = True
                break
            if p%i == 0:
                p = p//i
                if p == 1:
                    s = 1
                if i not in fact:
                    fact[i] = 1
                else:
                    fact[i] += 1
                break
    ans = 1
    for i in fact:
        if fact[i] >= n:
            ans = ans*i**(fact[i]//n)
    print(ans)
### BUGGY CODE ###

N=int(input())
listA = list(map(int,input().split()))[::-1]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

# Nの倍数の数を格納する辞書
baisuu = {i:0 for i in range(1,N+1)}
M=0
out_list=[]

a=listA

half=N//2

for i,ai in enumerate(a):
    now_index=N-i
    if now_index > half:
        if ai==1:
            soinsuu = make_divisors(now_index)
            out_list.append(now_index)
            M+=1
            for so in soinsuu:
                baisuu[so]+=1
    else:
        if baisuu[now_index]%2!=ai:
            out_list.append(now_index)
            M+=1
            soinsuu = make_divisors(now_index)
            for so in soinsuu:
                baisuu[so]+=1

print(M)
if M>0:
    out_list=sorted(out_list)
    print(" ".join(list(map(str, out_list))))

### FIXED CODE ###

N=int(input())
a = list(map(int,input().split()))[::-1]

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

# Nの倍数の数を格納する辞書
baisuu = {i:0 for i in range(1,N+1)}
M=0
out_list=[]

half=N//2

for i,ai in enumerate(a):
    now_index=N-i
    if now_index > half:
        if ai==1:
            soinsuu = make_divisors(now_index)
            out_list.append(now_index)
            M+=1
            for so in soinsuu:
                baisuu[so]+=1
    else:
        if baisuu[now_index]%2!=ai:
            out_list.append(now_index)
            M+=1
            soinsuu = make_divisors(now_index)
            for so in soinsuu:
                baisuu[so]+=1

print(M)
if M>0:
    out_list=sorted(out_list)
    print(" ".join(list(map(str, out_list))))
### BUGGY CODE ###

n, x = map(int, raw_input().split())
a = map(int, raw_input().split())
ans = []
b = a[:]
for k in range(n):
    for i in range(n):
        b[i] = min(a[i-k],b[i])
    ans.append(k*x+sum(b))
print min(ans)


### FIXED CODE ###

def solve(n, x, a):
	costs = []
	cost_min = 0
	for k in range(n):
		if k == 0:
			costs = a.copy()
		else:
			for i in range(n):
				costs[i] = min(costs[i], a[(i-k)%n])
		cost_k = sum(costs) + k*x
		if k == 0:
			cost_min = cost_k
		else:
			cost_min = min(cost_min, cost_k)
			if cost_min != cost_k:
				break
		if cost_min < (k+1) *x:
			break
 
	return cost_min
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
print(solve(n,x,a))
### BUGGY CODE ###

A, B, C, X, Y = tuple(map(int, input().split()))

A + 2 // C > X
B + 2 // C > Y

# 大きな値で初期化
TOTAL_MIN = A * X + B * Y + C * (X+Y) * 2
for i in range(X+1):
    for j in range(Y+1):
        k = max(X - i, Y - j) * 2
        total_tmp = A * i + B * j + C * k
        if total_tmp < TOTAL_MIN:
            TOTAL_MIN = total_tmp

print(TOTAL_MIN)


### FIXED CODE ###

A, B, C, X, Y = tuple(map(int, input().split()))

# 大きな値で初期化
TOTAL_MIN = A * X + B * Y + C * (X+Y) * 2

for a in range(X + 1):
    c = (X - a) * 2
    if c // 2 < Y:
        if B < 2 * C:
            b = Y - c // 2
        else:
            b = 0
            c = max(c, Y * 2) 
    else:
        b = 0
    
    total_tmp = A * a + B * b + C * c
    if total_tmp < TOTAL_MIN:
        TOTAL_MIN = total_tmp
        

print(TOTAL_MIN)
### BUGGY CODE ###

def main():
    N = int(input())
    lst = list(map(int, input().split()))
    ans = 1

    if 0 in lst:
        print(0)
        return 0
    for i in range(N):
        ans *= lst[i]
    if ans > 10 ** 18:
        print(-1)
    else:
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    _ = input()
    lst = list(map(int, input().split()))
    ans = 1

    if 0 in lst:
        print(0)
        exit()
    for i in lst:
        ans *= i
        if ans > 10 ** 18:
            print(-1)
            exit()
    print(ans)


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

import heapq
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    heapq.heapify(A)
    for _ in range(M):
        b, c = map(int, input().split())
        for i in range(b):
            if A[0] < c:
                heapq.heappushpop(A, c)
            else:
                break
    return sum(A)
print(main())



### FIXED CODE ###

import heapq
def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = [(1, -i) for i in A]
    heapq.heapify(A)
    for _ in range(M):
        b, c = map(int, input().split())
        B.append((b,-c))
    B.sort(key=lambda x: x[1])
    t = 0
    i = 0
    tl = []
    while t < N:
        tl.extend([-B[i][1]] * B[i][0])
        t += B[i][0]
        i += 1
    return sum(tl[:(N)])
print(main())
### BUGGY CODE ###

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

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i*100)%waru!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1


### FIXED CODE ###

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

if d==0:
  cnt=0
  i=1
  while 1:
    if i%100!=0:
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
else:
  cnt=0
  i=1
  waru=100**d
  while 1:
    if i%waru==0 and (i//waru)%100 !=0 :
      cnt+=1
    if cnt==n:
      print(i)
      exit()
    i+=1
### BUGGY CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
inputs = [[int(i) for i in input().split()] for _ in range(M)]

alist.sort()
inputs.sort()

for i in inputs:
    if alist[i[0]-1] < i[1]:
        alist = [i[1]] * i[0] + alist[i[0]:]
    else:
        limit=bisect.bisect_left(alist, i[1])
        alist = [i[1]] * limit + alist[limit:]
    alist.sort()

print(sum(alist))




### FIXED CODE ###

import bisect

N, M = [int(i) for i in input().split()]
alist = [int(i) for i in input().split()]
alist.sort()
inputs = [[int(i) for i in input().split()] for j in range(M)]
inputs.sort(key=lambda x:x[1], reverse=True)

for i in range(N):
    if len(inputs) == 0:
        break
    if inputs[0][1] > alist[i]:
        alist[i] = inputs[0][1]
        inputs[0][0] -= 1
        if inputs[0][0] == 0:
            inputs.pop(0)
    else:
        break
print(sum(alist))
### BUGGY CODE ###

#141d
from collections import deque
import bisect

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list)>1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    while 1:
        #print(A_list,highest)
        if highest>=next_highest:
            if M > 0:
                highest /= 2
                M -= 1
            else:
                A_list.append(highest)
                break
        else:
            bisect.insort(A_list,highest)
            highest = A_list.pop()
            next_highest = A_list[-1]

    A_list = [int(A) for A in A_list]
    print(sum(A_list))
else:
    while 1:
        if M > 0:
            A_list[-1] /= 2
            M -= 1
        else:
            print(int(A_list[-1]))
            break

### FIXED CODE ###

#141d
from collections import deque
import bisect
import math

N,M = map(int, input().split()) #1≤N,M≤10^5
A_list = list(map(int, input().split()))

#→高額なものに割引券を使った方が良い
if len(A_list) > 1:
    A_list.sort(reverse=False)
    highest = A_list.pop()
    next_highest = A_list[-1]

    discounted_deque = deque()

    while 1:
        use_tickets = math.ceil(math.log(highest/next_highest)/math.log(2))
        if use_tickets == 0:
            use_tickets = 1
        elif use_tickets > M:
            use_tickets = M
            
        highest /= pow(2,use_tickets)
        M -= use_tickets
        
        if M!= 0:
            discounted_deque.appendleft(highest)
            
            if len(A_list) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    highest = A_list.pop()
                else:
                    highest = discounted_deque.pop()
            else:
                highest = discounted_deque.pop()
                
            if len(A_list) > 0 and len(discounted_deque) > 0:
                if A_list[-1] > discounted_deque[-1]:
                    next_highest = A_list[-1]
                else:
                    next_highest = discounted_deque[-1]
            elif len(A_list) == 0 and len(discounted_deque) > 0:
                next_highest = discounted_deque[-1]
            elif len(A_list) > 0 and len(discounted_deque) == 0:
                next_highest = A_list[-1]
            
        else:
            A_list.append(highest)
            break

    A_list = [int(A) for A in A_list]
    discounted_list = [int(B) for B in discounted_deque]
    
    print(sum(A_list)+sum(discounted_list))
else:
    A_list[-1] = A_list[-1]//(pow(2,M))
    print(A_list[-1])
### BUGGY CODE ###

N=int(input())
X=list(input())
m=0
onecount=0
for i in range(N):
  d=N-1-i
  if X[i]=='1':
    m+=2**d
    onecount+=1

def f(x):
  result={}
  result[0]=0
  result[1]=1
  if x in result:
    return result[x]
  else:
    a=str(bin(x))
    b=a.count('1')
    d=x%b
    return f(d)+1
  
for i in range(N):
  d=N-1-i
  if X[i]=='0':
    D=m+2**d
  else:
    D=m-2**d
  print(f(D))

### FIXED CODE ###

N=int(input())
X=input()
a=int(X,2)

def popcount(x):
  return bin(x).count("1")
p=X.count('1')

pl=a%(p+1)
if p!=1:
  mi=a%(p-1)

def f(x):
  if x==0:
    return 1
  else:
    return f(x%popcount(x))+1

for i in range(N):
  if X[i]=='0':
    b=pl
    b+=pow(2,N-i-1,p+1)
    b%=p+1
  else:
    if p!=1:
      b=mi
      b-=pow(2,N-i-1,p-1)
      b%=p-1
    else:
      print(0)
      continue
  print(f(b))
### BUGGY CODE ###

s = raw_input()
K = input()

alpha = [chr(i) for i in range(97,97+26)]

for moji in range(len(s)):
	if alpha.index(s[moji]) != 0:
		if K >= 26-alpha.index(s[moji]):
			K = K - (26-alpha.index(s[moji]))
			s = s[:moji] + 'a' + s[moji+1:] 

if K>0:
	last_char = alpha[ alpha.index(s[-1]) + (K % 26) ]
	s = s[:-1] + last_char

print s

### FIXED CODE ###

s = raw_input()
K = input()

alpha = [chr(i) for i in range(97,97+26)]

i = 0
while K>=26 and i<len(s)-1:
	if alpha.index(s[i]) != 0:
		K = K - (26 - alpha.index(s[i]))
		s = s[:i] + 'a' + s[i+1:]
	i=i+1

for moji in range(i, len(s)):
	if alpha.index(s[moji]) != 0:
		if K >= 26-alpha.index(s[moji]):
			K = K - (26-alpha.index(s[moji]))
			s = s[:moji] + 'a' + s[moji+1:] 

if K>0:
	last_char = alpha[ alpha.index(s[-1]) + (K % 26) ]
	s = s[:-1] + last_char

print s
### BUGGY CODE ###

import heapq
INF = 10 ** 16


def dijkstra(n, town, k, start):
    d = []
    used = []
    for i in range(n):
        d.append(INF)
        used.append(False)
    d[start] = 0
    # 都市kで交換した時の円またはスヌークのの最小値
    while True:
        v = -1
        for u in range(n):
            if not used[u] and (v == -1 or d[u] < d[v]):
                v = u
        if v == -1:
            break
        used[v] = True
        for u in range(len(town[v])):
            if d[v] + town[v][u][k] < d[town[v][u][0]]:
                d[town[v][u][0]] = d[v] + town[v][u][k]
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    town = []

    for i in range(n):
        town.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        town[fro].append((to, a, b))
        town[to].append((fro, a, b))

    a = dijkstra(n, town, 1, s)
    b = dijkstra(n, town, 2, t)

    total = []
    for i in range(n):
        heapq.heappush(total, (a[i] + b[i], i + 1))
    count = 0
    mon, year = heapq.heappop(total)
    for i in range(n):
        while year <= i:
            mon, year = heapq.heappop(total)
        print(money - mon)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heapify, heappop, heappush


def dijkstra(n, train, start):
    d = []
    queue = []
    INF = 10 ** 16
    for i in range(n):
        d.append(INF)
    d[start] = 0
    heapify(queue)
    heappush(queue, (0, start))
    # 都市kに行く時の円またはスヌークのの最小値
    while len(queue) != 0:
        distance, v = heappop(queue)
        if d[v] < distance:
            continue
        for u in range(len(train[v])):
            if d[train[v][u][0]] > d[v] + train[v][u][1]:
                d[train[v][u][0]] = d[v] + train[v][u][1]
                heappush(queue, (d[train[v][u][0]], train[v][u][0]))
    return d


def main():
    n, m, s, t = map(int, input().split())
    s -= 1
    t -= 1
    money = 10 ** 15
    train_en = []
    train_snuuk = []

    for i in range(n):
        train_en.append([])
        train_snuuk.append([])
    for i in range(m):
        fro, to, a, b = map(int, input().split())
        fro -= 1
        to -= 1
        train_en[fro].append((to, a))
        train_en[to].append((fro, a))
        train_snuuk[fro].append((to, b))
        train_snuuk[to].append((fro, b))

    a = dijkstra(n, train_en, s)
    b = dijkstra(n, train_snuuk, t)

    cost_sum = []
    for i in range(n):
        cost_sum.append((a[i] + b[i], i + 1))
    heapify(cost_sum)
    m, y = heappop(cost_sum)
    for i in range(n):
        while y <= i:
            m, y = heappop(cost_sum)
        print(money - m)


if __name__ == '__main__':
    main()
### 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(1,n+1):
  if i in a:
    continue
  else:
    b[i]+=b[i-1]
    if i>1:b[i]+=b[i-2]
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))
### BUGGY CODE ###

from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = []
alr.append(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i in alr:
            continue
        else:
            que.append(i)
            alr.append(i)
            px[i] += sumq
print(*px)

### FIXED CODE ###

from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = set()
alr.add(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i in alr:
            continue
        else:
            que.append(i)
            alr.add(i)
            px[i] += sumq
print(*px)
### BUGGY CODE ###

N = int(input())

A = list(map(int, input().split()))
sum=1
for n in A:
    sum=sum*n

if sum>1000000000000000000:
    sum = -1

print(sum)




### FIXED CODE ###


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

if 0 in A:
    print(0)
else:
    for n in range(N):
        sum = sum * A[n]
        if sum>1000000000000000000:
            print(-1)
            break
    else:
        print(sum)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
# chech with no break
finish = False
def check(A, cnt=0):
  N = len(A)
  #print(A)
  for i, a in enumerate(A):
    if a != N and i != N - 1:
      continue
    if a == N and i != N - 1:
      return False
    if A[N - 1] == N:
      #print("debug")
      if cnt == 0:
        print(0)
      return True
  return False
finish = check(A)
cnt = 0
while finish is False:
  # Miss break from the large number
  #m = max(A)
  #i = A.index(m)
  i = 0
  if len(A) > 1:
    A.pop(i) # remove
    cnt += 1
    finish = check(A, cnt)
  else:
    break
  i += 1
if finish is True and cnt != 0:
  print(cnt)
if finish is False:
  print(-1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt, i = 0, 1
for a in A:
  if a == i:
    i += 1
  else:
    cnt += 1
print(cnt if cnt != N else -1)
### BUGGY CODE ###

n = int(input())
a_int = list(map(int, input().split()))
squ = 0
for i in range(0, n):
    for j in range(i+1, n):
        squ += a_int[i] * a_int[j]
ans = squ % (10 ** 9 + 7)
print(ans)

### FIXED CODE ###

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

squ = 0
num = 10 ** 9 + 7

a_sum = 0
for i_sum in range(1, n):
    a_sum += a_int[i_sum]

for i in range(0, n-1):
    squ += a_int[i] * a_sum
    a_sum -= a_int[i+1]

ans = squ % num
print(ans)
### BUGGY CODE ###

import itertools

def mod(x):
  return x%((10**9)+7)
n=int(input())
a_list=list(map(int,input().split()))
sum_list=[]
sum_list=[i[0]*i[1] for i in itertools.combinations(a_list,2)]
s=sum(sum_list)
s=mod(s)
print(s)

### FIXED CODE ###

import itertools

n=int(input())
a_list=list(map(int,input().split()))
sum=0
ps = list(itertools.accumulate(a_list))
for i in range(n-1):
  sum+=a_list[i]*(ps[n-1]-ps[i])

s=sum%(10**9+7)
print(s)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
for i in range(n):
  tmp = sorted(li[:i]+li[i+1:])
  print(tmp[int(n/2)-1])

### FIXED CODE ###

n = int(input())
li = list(map(int,input().split()))
lis = sorted(li)
m = lis[int(n/2)-1]
M = lis[int(n/2)]
for i in range(n):
  if li[i] <= m:
    print(M)
  else:
    print(m)
### BUGGY CODE ###

def build_cost_table(n):
    ret = [[-1] * (n + 1) for _ in range(n + 1)]  # J字にコスト-1の区画を設ける
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            if ~ret[r][c]: continue
            dc = min(c, n - 1 - c)
            ret[r][c] = ret[n - 1 - r][c] = ret[n - 1 - r][n - 1 - c] = ret[r][n - 1 - c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [[1] * N for _ in range(N)]  # 着席

    ans = 0
    for pi in p:
        pi_r, pi_c = divmod(pi, N)

        hpi = H[pi_r][pi_c]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi_r][pi_c] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi_r, pi_c, hpi))
        while dq:
            r, c, h = dq.popleft()
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if H[nr][nc] > h:
                    H[nr][nc] = h
                    dq.append((nr, nc, h + S[nr][nc]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def build_cost_table(n):
    ret = [-1] * (n ** 2)
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            dc = min(c, n - 1 - c)
            ret[r * n + c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [1] * (N ** 2)  # 着席

    ans = 0
    for pi in p:
        hpi = H[pi]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


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

import heapq


class Value:
    def __init__(self, val, f):
        self.val = val
        self.key = f(val)

    def __lt__(self, other):
        return self.key < other.key

    def __repr__(self):
        return repr(self.val)


class Heapq:
    def __init__(self, arr, f=lambda x: x):
        for i in range(len(arr)):
            arr[i] = Value(arr[i], f)
        self.func = f
        self.hq = arr
        heapq.heapify(self.hq)

    def pop(self):
        return heapq.heappop(self.hq).val

    def push(self, a):
        heapq.heappush(self.hq, Value(a, self.func))

    def top(self):
        return self.hq[0].val


n = int(input())
a = [int(input()) for _ in range(n)]
if a[0] > 0:
    print(-1)
    exit(0)
hq = Heapq([], f=lambda x: (-a[x], x))
for i, x in enumerate(a):
    if x > 0:
        hq.push(i)
ans = 0
while hq.hq:
    i = hq.pop()
    if a[i] - 1 == a[i - 1]:
        ans += 1
        a[i] = (a[i + 1] - 1 if i != n - 1 else 0)
        if a[i] > 0:
            hq.push(i)
    else:
        print(-1)
        exit(0)
print(ans)


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)] + [0]
if a[0] > 0:
    print(-1)
else:
    ans = 0
    for i in range(n):
        if a[i] < a[i + 1] - 1:
            print(-1)
            break
        elif a[i] >= a[i + 1]:
            ans += a[i]
    else:
        print(ans)
### BUGGY CODE ###

a=input()
b=input().split(" ")
sum1=1

for i in range(int(a)):
	sum1=sum1*int(b[i])

if sum1>1000000000000000000:
	print("-1")
else:
	print(sum1)


### FIXED CODE ###

a=int(input())
b=input().split(" ")
sum1=1

if "0" in b:
	print("0")
else:
	for i in range(a):
		sum1=sum1*int(b[i])
		if sum1>10**18:
			sum1=-1
			break
	print(sum1)
### BUGGY CODE ###

S=input()
Q=int(input())
cnt=0
for i in range(Q):  
  L=list(input().split())  
  if L[0]=="1":
    cnt+=1
  else:
    if cnt%2==1:
      S=S[::-1]
      cnt=0
    if L[1]=="1":
      S=L[2]+S
    else:
      S=S+L[2]
if cnt%2==1:
  S=S[::-1]
print(S)

### FIXED CODE ###

import collections

s = collections.deque(list(input()))
q = int(input())
rev = 0
for i in range(q):
    tfc = list(input().split())
    if tfc[0]=='1':
        rev = abs(rev-1)
    else:
        t,f,c = tfc
        if rev:
            if f=='1':
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f=='1':
                s.appendleft(c)
            else:
                s.append(c)
if rev:
    t = []
    for i in range(len(s)):
        t.append(s.pop())
    print(''.join(t))
else:
    print(''.join(s))
'''
初期文字列 s が与えられ q 個のクエリを処理した後の文字列を求めます。
10^100回繰り返す根気があるなら自分でやってくれと思わなくもないです。
さて、各クエリではまず t が与えられます。t=1の時文字列を反転させます。
t=2の時はさらに f,c が与えられ、f=1の時文字列の先頭にcを加えます。
f=2の時文字列の末尾にcを加えます。
愚直に行おうとすると文字列の反転で O(len(s))、先頭への追加で 
O(len(s)) かかってしまい間に合いません。
そこでcollections.dequeを利用します。先頭、末尾への追加をO(1) で行えます。
注意する点は反転させると追加する位置が逆になることです。
なので現在の状態を管理しておく必要があります。
同様に出力する時も最終的な向きによって出力する順番が逆になります。
'''