Harryxun/stf_run huggingface dataset:
N=int(input())
b=list(map(int, input().split()))

a=[]

for i in range(N):
  if i+1 < b[i]:
    a=[0]*1
    a[0]= -1
    break
  a.insert(b[i],b[i])

for j in range(N):
  print(a[j])

### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
b.reverse()
ans_set = [0]*n
ans = 0

for i in range(n):
    if ans == -1:
        break
    
    for j in range(n):
        if b[j] == n-j:
            ans = b.pop(j)
            ans_set[n-1] = ans
            n -= 1
            break
            
        elif b[j] > n-j:
            ans = -1
            print(ans)
            break

        if n == 0:
            break

if ans != -1:
    for k in ans_set:
        print(k)
def main():
  import sys
  input = sys.stdin.readline
  n=int(input())
  a=sorted(list(map(int,input().split())))
  mod=pow(10,9)+7
  x=[0]*61
  for i in a:
    i=bin(i)
    l=len(i)
    for j in range(1,l-1):
      if i[-j]=='1':
        x[j]+=1
  ans=0
  for i in range(1,l+1):
    if x[i]>0:
      ans+=pow(2,i-1,mod)*(x[i]%mod)*((n-x[i])%mod)%mod
      ans%=mod
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  import numpy as np
  n=int(input()) 
  a=np.array(list(map(int,input().split())))
  mod=pow(10,9)+7
  ans=0
  
  for i in range(60):
    x=np.count_nonzero(a & 1)
    ans+=pow(2,i,mod)*x*(n-x)
    ans=ans%mod
    a=a>>1
  print(ans)
if __name__=='__main__':
  main()
def fiv(n):
    return (((1+(5)**(1/2))/2)** n - ((1-(5)**(1/2))/2)** n)/(5**(1/2))

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

p = [0] * (m + 1) #broken間の登り方list

for i in range(m + 1):
    if i == 0: #a1 さいしょ
        if broken[0] == 1 or 2:
            p[0] = 1
        else:
            p[0] = fiv(broken[0] -1)
    if i == m: #am さいご
        if broken[m] == n - 1 or m - 2:
            p[m] = 1
        else:
            p[m] = fiv(n - broken[0])
    
    else:
        p[i] = fiv(broken[i] - broken[i - 1] - 1)

ans = 1
for i in range(m + 1):
    ans = ans * p[i]

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
dp = [-1 for i in range(n + 1)]
dp[0], dp[1] = 1, 1
for _ in range(m):
    dp[int(input())] = 0
for i in range(2, n + 1):
    if dp[i] != 0:
        dp[i] = (dp[i - 1] + dp[i - 2]) % mod
print(dp[n])
# 愚直な方法: O(n^2)
n = int(input())
a = np.array(list(map(int, input().split())))
cnt = 0
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if abs(i-j) == (a[i-1]+a[j-1]):
            cnt += 1
print(cnt)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
ci = defaultdict(int)
cj = defaultdict(int)
for i in range(n):
    ci[a[i]+i] += 1
    cj[i-a[i]] += 1
cnt = 0
for k in ci.keys():
    cnt += ci[k] * cj[k]
print(cnt)
n=int(input())
l=list(map(int,input().split()))
count=0
for i in range (n-2):
    for j in range (i+1,n-1):
        if l[i]==l[j]:
            continue
        l[i]+l[j]
        for k in range (j+1,n):
            if l[k]==l[i] or l[k]==l[l]:
                continue
            if l[k]<l[i]+l[j] and l[i]<l[j]+l[k] and l[j]<l[k]+l[i] :
                count+=1
print(count)
    


### FIXED CODE ###

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

count=0
for i in range (n-2):
    for j in range (i+1,n-1):
        if l[i]==l[j]:
            continue
        for k in range (j+1,n):
            
            if l[k]==l[i] or l[k]==l[j]:
                continue
            if l[k]<l[i]+l[j] and l[i]<l[j]+l[k] and l[j]<l[k]+l[i] :
                count+=1
print(count)
import sympy as sp
import copy

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

def calc_gcd(list):
    ans = list[0]
    for i in range(1,n-1):
        ans = sp.gcd(ans,list[i])
    return ans

#a = [1,2,3,4,5,6,7]

for j in range(n):
    b= copy.copy(a)
    b.pop(j)
    nlist.append(calc_gcd(b))

#print(nlist)
print(max(nlist))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
lgcd = [0]*N
rgcd = [0]*N
from fractions import gcd
#def gcd(a,b):
#    if b == 0:return a
#    else:return gcd(b, a%b)

temp_lgcd = A[0]
for i in range(N):
    temp_lgcd = gcd(temp_lgcd,A[i])
    lgcd[i] = temp_lgcd

temp_rgcd = A[-1]
for i in range(N-1,-1,-1):
    temp_rgcd = gcd(temp_rgcd,A[i])
    rgcd[i] = temp_rgcd

ans = 0
for i in range(N):
    if i == 0:
        calc_gcd = rgcd[1]
    elif i == N-1:
        calc_gcd = lgcd[-2]
    else:
        calc_gcd = gcd(lgcd[i-1],rgcd[i+1])
    ans = max(ans,calc_gcd)
print(ans)
import math
import decimal
decimal.getcontext().prec = 22

#getcontext().prec=20
a,b,h,m=map(int,input().split())
a=decimal.Decimal(a)
b=decimal.Decimal(b)
h=decimal.Decimal(h)
m=decimal.Decimal(m)

#print(a,b,h,m)

ang1=decimal.Decimal(360*(h/12)+30*m/60)
ang2=decimal.Decimal(360*m/60)
ang=decimal.Decimal(abs(ang1-ang2))
print(ang)
if ang>=180.0:
    ang=ang-180.0

#print(ang)
ans = ((a)**2 + (b)**2 - decimal.Decimal(2.0)*(a)*(b)*decimal.Decimal(math.cos(math.radians(ang))))
ans = (math.sqrt(ans))
#print(math.cos(math.radians(ang)))

print(ans)

### FIXED CODE ###

import math
#import decimal
#decimal.getcontext().prec = 12

#getcontext().prec=20
a,b,h,m=map(int,input().split())
#a=decimal.Decimal(a)
#b=decimal.Decimal(b)
#h=decimal.Decimal(h)
#m=decimal.Decimal(m)

#print(a,b,h,m)

#ang1=decimal.Decimal(360*(h/12)+30*m/60)
#ang2=decimal.Decimal(360*m/60)
#ang=decimal.Decimal(abs(ang1-ang2))
ang1=360*(h/12)+30*m/60
ang2=360*m/60
ang=abs(ang1-ang2)
#print(ang)
if ang>=180.0:
#    ang=ang-180.0
    ang=360.0-ang

#print(ang)
#ans = ((a)**2 + (b)**2 - decimal.Decimal(2.0)*(a)*(b)*decimal.Decimal(math.cos(math.radians(ang))))
ans = a**2 + b**2 - 2.0*a*b*math.cos(math.pi*ang/180.0)
ans = math.sqrt(ans)
#print(math.cos(math.radians(ang)))

print(ans)
rt numpy as np
N = input()
list = list(map(int,input().split(' ')))

list = np.array(list)
A = list[list%2 == 0]
B = np.unique(np.append(list[list%6 == 0],(list[list%10 == 0])))

if len(A) ==0:
        print('APPROVED')
elif len(B) ==0:
    print('DENIED')
else:
    if len(A) == len(B) :
        print('APPROVED')
    else:
        print('DENIED')


### FIXED CODE ###

import numpy as np
N = input()
list = list(map(int,input().split(' ')))

list = np.array(list)
A = np.unique(list[list%2 == 0])
B = np.unique(np.append(list[list%6 == 0],(list[list%10 == 0])))

if len(A) ==0:
        print('APPROVED')
elif len(B) ==0:
    print('DENIED')
else:
    if len(A) == len(B) :
        print('APPROVED')
    else:
        print('DENIED')
import sys

parents = [-1] * 20000

def main():

    input = sys.stdin.readline

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


    for _ in range(M):
        A,B = map(int,input().split())

        A = A - 1
        B = B - 1

        union(A,B)

    ans = 1
    for i in range(20000):
        ans = max(ans,size(i))

    print(ans)

def find(x):
    if parents[x] < 0:
        return x
    else:
        parents[x] = find(parents[x])
        return parents[x]

def union(x, y):
    x = find(x)
    y = find(y)

    if x == y:
        return

    if parents[x] > parents[y]:
        x, y = y, x

    parents[x] += parents[y]
    parents[y] = x

def size(x):
    return -parents[find(x)]


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys


def main():

    input = sys.stdin.readline

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

    AB = [list(map(int,input().split())) for _ in range(M)]

    UF = UnionFind(N)

    for i in range(M):
        A,B = AB[i]

        A = A - 1
        B = B - 1

        UF.union(A,B)


    ans = 1
    for i in range(N):
        ans = max(ans,UF.size(i))

    print(ans)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

if __name__ == "__main__":
    main()
n = int(input())
aL = sorted(list(map(int, input().split(" "))))

dp = [False for _ in range(100001)]

if len(aL) == 1 and n != 1:
    print(0)
    exit()

ans = 0
for a in aL:
    if not dp[a]:
        ans += 1
    c = 1
    while a * c <= 100000:
        dp[a * c] = True
        c += 1

print(ans)


### FIXED CODE ###

n = int(input())
aL = sorted(list(map(int, input().split(" "))))
# aL = sorted(list(set(aLP)))

dp = [False for _ in range(1000001)]

d = {}
for a in aL:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

ans = 0
for a in aL:
    if dp[a]:
        continue
    if d[a] > 1:
        c = 1
        while a * c <= 1000000:
            dp[a * c] = True
            c += 1
        continue
    ans += 1

    c = 1
    while a * c <= 1000000:
        dp[a * c] = True
        c += 1

print(ans)
n=int(input())
x=input()
p=0
chk1=0
chk2=0
b=x.count("1")
for i,j in enumerate(x[::-1]):
    if j=="1":
         chk1+=pow(2,i,b+1)
         chk2+=pow(2,i,b-1)
l=[]
chk1=chk1+b+1
chk2=chk2+b-1
for i,j in enumerate(x[::-1]):
    a1=pow(2,i,b+1)
    a2=pow(2,i,b-1)
    if j=="0":
        t=chk1+a1
    else:
        t=chk2+b-1-a2
    #print("#",t)
    ans=0
    while t:
        t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l:
    print(i)


### FIXED CODE ###

n=int(input())
x=input()
chk0=chk1=chk2=0
b=x.count("1")
if b==1 and x=="1":
    print(0)
    exit()
elif b==1:
    for i in range(n):
        if i==n-1: print(2)
        elif x[i]=="0": print(1)
        else: print(0)
    exit()
for i,j in enumerate(x[::-1]):
    if j=="1":
        chk1+=pow(2,i,b+1)
        if b>1: chk2+=pow(2,i,b-1)
        else: chk2=0
l=[]
for i,j in enumerate(x[::-1]):
    if b: a1=pow(2,i,b+1)
    else: a1=1
    if b>1: a2=pow(2,i,b-1)
    else: a2=1
    if j=="0":
        t=chk1+a1
    else:
        if b>1: t=chk2+b-1-a2
        else: t=0
    ans,f=0,1
    while t:
        if f:
            if j=="0": t%=(b+1)
            else: t%=(b-1)
            f=0
        else:
            t%=bin(t).count("1")
        ans+=1
    l.append(ans)
for i in l[::-1]:
    print(i)
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
  if A[i] < 0:
    A[i] *= -1
    A[i + 1] *= -1
print(sum(A))

### FIXED CODE ###

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

for i in range(N):
  if A[i] < 0:
    count += 1
    A[i] *= -1
print(sum(A) if count % 2 == 0 else sum(A) - min(A) * 2)
n,k = map(int, input().split())
a = list(map(int, input().split()))
if 0 in a:
  a.remove(0)
  n -= 1
  k -= 1
m = 300000000
for i in range(n+1-k):
  if a[i+k-1] < 0:
    x = -a[i]
  if a[i] > 0:
    x = a[i+k-1]
  else:
    x = (a[i+k-1]-a[i]) + min(-a[i],a[i+k-1])
  m = min(m,x)
print(m)

### FIXED CODE ###

n,k = map(int, input().split())
a = list(map(int, input().split()))
if 0 in a:
  a.remove(0)
  n -= 1
  k -= 1
if k == 0:
  print(0)
  exit()
m = 300000000
for i in range(n+1-k):
  if a[i+k-1] < 0:
    x = -a[i]
  elif a[i] > 0:
    x = a[i+k-1]
  else:
    x = (a[i+k-1]-a[i]) + min(-a[i],a[i+k-1])
  m = min(m,x)
print(m)
s = input()

s_l=s.sorted()
if s_l[0]!=s_l[1] or s_l[2]!=s_l[3] or s_l[0]==s[3]:
	print("No")
else :
	print("Yes")


### FIXED CODE ###

s = sorted(input())


if s[0]!=s[1] or s[2]!=s[3] or s[0]==s[3]:
	print("No")
else :
	print("Yes")
def solve(string):
    n, k, *v = map(int, string.split())

    def dfs(deq, get, count, minus):
        if count == k:
            return sum(get)
        op1 = dfs(deq[1:], get + [deq[0]], count + 1, minus + (deq[0] < 0))
        op2 = dfs(deq[:-1], get + [deq[-1]], count + 1, minus + (deq[-1] < 0))
        m = min(get) if len(get) > 0 else 0
        op3 = 0 if m >= 0 else dfs(deq[:], sorted(get)[1:], count + 1, minus - 1)
        return max(op1, op2, op3)

    return str(dfs(v[:], [], 0, 0))


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))


### FIXED CODE ###

def solve(string):
    n, k, *v = map(int, string.split())
    ans = 0
    for i in range(k + 1):
        for j in range(k - i + 1):
            base = sorted(v[:i] + v[max(n - k + i + j, i):])
            ans = max(ans, sum([b for l, b in enumerate(base) if b >= 0 or j <= l]))
    return str(ans)


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
import math

X,K,D = map(int, input().split())
tm = round(X/D)
if K <= tm:
  print(abs(X-D*K))
else:
  if (K-tm)%2==1:
    if math.modf(X/D)<0.5:
      print(abs(X-D*(tm+1)))
    else:
      print(abs(X-D*(tm-1)))
  else:
    print(abs(X-D*tm))

### FIXED CODE ###

X, K, D = map(int, input().split())
 
Xa = abs(X)
Xs = Xa // D
Xm = Xa % D
 
if (K <= Xs):
    print(abs(Xa-D*K))
elif (K-Xs) % 2 == 0:
    print(abs(Xm))
else:
    print(abs(D-Xm))
w=sorted(input())
if len(w)%2==1:
    print('No')
else:
    while len(w)>=2:
        if w.pop(0)!=w.pop(0):
            print('No')
            exit()
	print('Yes')

### FIXED CODE ###

w=sorted(input())
if len(w)%2==1:
    print('No')
else:
    while len(w)>=2:
        if w.pop(0)!=w.pop(0):
            print('No')
            exit()
    print('Yes')
import numpy as np

a = [list(map(int,input().split())) for _ in range(3)]

n = int(input())

b = list([int(input()) for _ in range(n)])

c = [[0]*3]*3

for k in b:
    for i in range(3):
        for j in range(3):
            if k == a[i][j]:
                c[i][j]=1

c = np.array(c)

if (max(c.sum(axis=0))==3) or (max(c.sum(axis=1))==3) or \
    (sum([a[i,i] for i in range(3)])==3) or (a[2,0]+a[1,1]+a[0,2]==3):
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import numpy as np

a = [list(map(int,input().split())) for _ in range(3)]

n = int(input())

b = list([int(input()) for _ in range(n)])

c = np.zeros(9).reshape(3,3)

for k in b:
    for i in range(3):
        for j in range(3):
            if k == a[i][j]:
                c[i,j]=1

if (max(c.sum(axis=0))==3) or (max(c.sum(axis=1))==3) or \
    (sum([c[i,i] for i in range(3)])==3) or (c[2,0]+c[1,1]+c[0,2]==3):
    print("Yes")
else:
    print("No")
S: str = input()
Q = int(input())

ANS = S

for _ in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        ANS = ANS[::-1]
    else:
        f, c = query[1:]
        if f == '1':
            ANS = c + ANS
        else:
            ANS = ANS + c

print(ANS)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

ANS = deque(S)

rev = 0

for _ in range(Q):
    query = input().split(' ')
    if len(query) == 1:
        rev = rev ^ 1
    else:
        f, c = int(query[1]), query[2]
        if (f - 1) ^ rev:
            ANS.append(c)
        else:
            ANS.appendleft(c)

if rev:
    ANS.reverse()

print(''.join(ANS))
n,k=map(int,input().split())
l=list(map(int,input().split()))
final=[0]*n
if k>=n:
  print(abs(l[n-1]-l[0]))
else:   
   for i in range(1,k+1):
      final[i]=abs(l[i]-l[0])
  
   for i in range(k+1,n):

      mini=10**9+1



  
      x=k
      for j in range(1,x+1):

           mini=min(mini,final[i-j]+abs(l[i]-l[i-j]))
      final[i]=mini
    print(final[-1])


### FIXED CODE ###

n,k=map(int,input().split())
l=list(map(int,input().split()))
final=[0]*n
if k>=n:
  print(abs(l[n-1]-l[0]))
else:   
   for i in range(1,k+1):
      final[i]=abs(l[i]-l[0])
  
   for i in range(k+1,n):

      li=[abs(l[i]-l[ik])+final[ik] for ik in range(i-1,i-k-1,-1) ]
      final[i]=min(li)
   print(final[-1])
x = int(input())
i = 0
while x-i % i != 0:
  i+= 1
a += i
b += x - i
print(a,b)

### FIXED CODE ###

x = int(input())
for i in range(-500,500):
  for j in range(-500,500):
    a = pow(i,5)
    b = pow(j,5)
    if(x == a - b):
      print(i,j)
      exit(0)
while True:
      x=input().split(" ")
      a=int(x[0])
      op=x[1]
      b=int(x[2])
      if (op =="+"):
        print(a+b)
      elif (op=="-"):
          print(a-b)
      elif (op=="*"):
          print(a*b)
      elif (op=="/"):
          print(a/b)
      elif (op =="?"):
         break


### FIXED CODE ###

while True:
    x=input().split(" ")
    a=int(x[0])
    op=x[1]
    b=int(x[2])
    if op == "+":
        print(a + b)
    elif op == "-":
        print(a - b)
    elif op == "*":
        print(a * b)
    elif op == "/":
        print(a // b)
    elif op == "?":
        break
import math
from functools import reduce
gcd = lambda l: reduce(math.gcd, l)
n, x = map(int, input().split())
c = [abs(x-int(i)) for i in input().split()]
print(gcd(c))

### FIXED CODE ###

import fractions
n, x = map(int, input().split())
idx = [abs(int(i) - x) for i in input().split()]
ans = idx[0]
if n == 1: pass
else:
    for i in range(1, n):
        ans = fractions.gcd(ans, idx[i])
print(ans)
r, g, b = map(int, input().split())

rgb = int(r*100 + g*10 + b)

if rgb % 4 == 0:
  print('YES)
else:
  print('NO)


### FIXED CODE ###

r, g, b = map(int, input().split())
 
rgb = int(r*100 + g*10 + b)
 
if rgb % 4 == 0:
  print('YES')
else:
  print('NO')
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)


### FIXED CODE ###

import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

N, = map(int, input().split())
ps = list(map(int, input().split()))
p2i = dict()
i = 0
for p in ps:
    if p not in p2i:
        i += 1
        p2i[p] = i
        continue
    x = p2i[p]
    break
X = min(x-1, i-1)
Y = min(N-x, N-i)
for i in range(1, N+2):
    print((cmb(N+1, i) - cmb(X+Y, i-1))%mod)
import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline
inf = 10**10



def dijkstra(repn, start, goal):
    dist = [inf for i in range(N + 1)] # 始点から各頂点までの最短距離を格納する
    
    dist[start] = 0
    q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    heapq.heappush(q, (0, start)) # 始点をpush

    while q:
        prov_cost, src = heapq.heappop(q) # pop
        
        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[src] < prov_cost:
            continue

        # 他の頂点の探索
        for dest in repn[src].values():
            cost = repn[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost # distの更新
                heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                
    return dist[goal]
        



N, M = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
    repn[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    if repn[l][r] == [] or repn[l][r] > c: #つまずきポイントその１
        repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == inf:
    print(-1)
else:
    print(d)


### FIXED CODE ###

import sys
import heapq
from collections import defaultdict
input = sys.stdin.readline
inf = 10**18



def dijkstra(repn, start, goal):
    dist = [inf for i in range(N + 1)] # 始点から各頂点までの最短距離を格納する
    
    dist[start] = 0
    q = []                  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
    heapq.heappush(q, (0, start)) # 始点をpush

    while q:
        prov_cost, src = heapq.heappop(q) # pop
        
        # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
        if dist[src] < prov_cost:
            continue

        # 他の頂点の探索
        for dest in repn[src]:
            cost = repn[src][dest]
            if dist[dest] > dist[src] + cost:
                dist[dest] = dist[src] + cost # distの更新
                heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                
    return dist[goal]
        



N, M = map(int, input().split())
repn = [defaultdict(list) for _ in range(N + 1)]
for i in range(2, N + 1):
    repn[i][i - 1] = 0
for _ in range(M):
    l, r, c = map(int, input().split())
    if repn[l][r] == [] or repn[l][r] > c: #つまずきポイントその１
        repn[l][r] = c

d = dijkstra(repn, 1, N)

if d == inf:
    print(-1)
else:
    print(d)
print(sum(map(int, input().split()))

### FIXED CODE ###

print(sum(map(int, input().split())))
days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
nums = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
while True:
    try:
        m, d = map(int, input().split())
        if not m:
            break
    except:
        break
    print(days[(sum(nums[:m - 1]) + d) % 7 + 2])

### FIXED CODE ###

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
nums = [31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
while True:
    try:
        m, d = map(int, input().split())
        if not m:
            break
    except:
        break
    print(days[(sum(nums[:m - 1]) + d + 2) % 7])
s,t= input().split()
a,b=map(int,input().split())
u=input()
if u==s:
  a-=1
else:
  t-=1
print(a,b)

### FIXED CODE ###

s,t= input().split()
a,b=map(int,input().split())
u=input()
if u==s:
  a-=1
else:
  b-=1
print(a,b)
import heapq

n,m = map(int,input().split())
lb = [[] for _ in range(10**5)]
for _ in range(n):
    a,b = map(int,input().split())
    lb[a].append(b)
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb[i]:
        heapq.heappush(q,b * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
lb = [[] for _ in range(10**5+5)]
for _ in range(n):
    a,b = map(int,input().split())
    lb[a].append(b)
res = 0
q = []
heapq.heapify(q)
for i in range(1,m+1):
    for b in lb[i]:
        heapq.heappush(q,b * (-1))
    if q:
        res += heapq.heappop(q) * (-1)

print(res)
n = int(input())
L, R = [0] * n, [0] * n
i = 0
for ipt in input().split():
    L[i] = i + ipt 
    R[i] = i - ipt
    i += 1
def make_dic(L):
    L_set = set(L)
    return dict([(i, L.count(i)) for i in L_set])
L_dic, R_dic = make_dic(L), make_dic(R)
cnt = 0
for Lk, Lv in L_dic.items():
    try:
        cnt += R_dic[Lk] * Lv
    except KeyError:
        pass
print(cnt)

### FIXED CODE ###

n = int(input())
L_dict, R_dict = {}, {}
i = 0
for ipt in input().split():
    try:
        L_dict[i + int(ipt)] += 1
    except KeyError:
        L_dict[i + int(ipt)] = 1
    try:
        R_dict[i - int(ipt)] += 1
    except KeyError:
        R_dict[i - int(ipt)] = 1
    i += 1
cnt = 0
for Lk, Lv in L_dict.items():
    try:
        cnt += R_dict[Lk] * Lv
    except KeyError:
        pass
print(cnt)