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

N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          c2.append(v)
    c = c2
  return -1
print(main())


### FIXED CODE ###

N, M = map(int, input().split())
a = [[] for i in range(N+1)]
for i in range(M):
  u, v = map(int, input().split())
  a[u].append(v)
#print(a)

S, T = map(int, input().split())
def main():
  c = [S]
  m = [[False, False, False] for i in range(N+1)]
  for count in range(1, 3*N+1):
    c2 = []
    for u in c:
      m[u][count %3] = True
      for v in a[u]:
        if (v == T and count %3 ==0):
          return count//3
        if not(m[v][(count+1) %3]):
          m[v][(count+1) %3]=True
          c2.append(v)
    c = c2
  return -1
print(main())
### BUGGY CODE ###

def ct(num):
    primel=[2]
    for i in range(2,num+1): 
        for e in primel:
            if i%e==0:break
        else:primel.append(i)
    return len(primel)        
    
while True:
    try:raw=[int(i) for i in input().split(" ")]
    except:break
    a=raw[0]
    print(str(ct(a)))

### FIXED CODE ###


import math

m=999999
s=int(math.sqrt(m)+1)
li=[0]*m
li[0]=1
for i in range(1,s):
    if li[i]==0:
        li[i*2+1::i+1]=[1 for e in range(len(li[i*2+1::i+1]))]
while True:
    try:n=int(input())
    except:break
    print(len([i for i in li[:n:] if i==0]))
### BUGGY CODE ###

import math

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

ceil = math.ceil

max_a = max(a)
target_length = max_a//2 + 1
min_a = 0

cnt = 0


while True:
    cnt += 1
    target_a = [ceil(x/target_length)-1 for x in a]
    if sum(target_a) > k:
        min_a = target_length
        target_length = (target_length + max_a)//2
    else:
        if target_length - min_a == 1:
            print(target_length)
            exit()
        max_a = target_length
        target_length = (target_length + min_a)//2

### FIXED CODE ###

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

max_a = max(A)
min_a = 0

while abs(max_a - min_a) > 1:
    cnt = 0
    target_length = (max_a + min_a)//2
    for a in A:
        cut_num = (a + target_length - 1)//target_length
        cnt += cut_num - 1
    if cnt > k:
        min_a = target_length
    else:
        if target_length - min_a == 1:
            print(target_length)
            exit()
        max_a = target_length

print(max_a)
### BUGGY CODE ###

N=int(input())
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
s=len(make_divisors(N-1))
for i in range(1,len(make_divisors(N))):
  q=N
  p=make_divisors(N)[i]
  while True:
    if q%p==0:
      q/=p
    else:
      break
  if (q-1)%p==0:
    s+=1
print(s-1)

### FIXED CODE ###

N=int(input())
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
s=len(make_divisors(N-1))
p=make_divisors(N)
for i in range(1,len(p)):
  q=N
  while True:
    if q%p[i]==0:
      q/=p[i]
    else:
      break
  if (q-1)%p[i]==0:
    s+=1
print(s-1)
### BUGGY CODE ###

import numpy as np

n = int(input())
A = list(map(int, input().strip().split()))
U = max(A) + 3
c = np.zeros((U),dtype=np.int64)
for a in A:
    c[a] += 1
#print(c)
x = np.array(range(1,c.max() + 3))
y = np.array(range(0,c.max() + 2))
q = x * y / 2
q = q.astype(np.int64)
#print(q)

s = 0
dex = np.where(c>0)
for i in dex[0]:
    s += q[c[i]-1]
#print(s)
for i in range(n):
    #print(A[i],q[max(0,c[A[i]]-1)],q[max(0,c[A[i]]-2)])
    print(s - q[max(0,c[A[i]]-1)] + q[max(0,c[A[i]]-2)])

### FIXED CODE ###

import numpy as np
import collections

n = int(input())
A = list(map(int, input().strip().split()))
C = collections.Counter(A)
#print(C)
s = 0
for v in C.values():
    s += v * (v-1) // 2
#print(s)
#print()
for i in range(n):
    print(s - C[A[i]] + 1)
### BUGGY CODE ###

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10 ** 9 + 7

dp = [[0] * (c + 1) for i in range(n + 1)]
dp[0][0] = 1

for ni in range(n):
    for cnt in range(c + 1):
        ru = 0
        for x in range(a[ni], b[ni] + 1):
            ru += pow(x, cnt, MOD)
            ru %= MOD
        for ci in range(c + 1):
            if ci - cnt < 0:
                continue
            dp[ni + 1][ci] += ru * dp[ni][ci - cnt] 
            dp[ni + 1][ci] %= MOD
print(dp[-1][-1])

### FIXED CODE ###

n, c = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0]*(c+1) for i in range(n+1)]
dp[0][0] = 1

ruiseki = [[0] * (410) for _ in range(c+1)]
for i in range(c + 1):
    for j in range(409):
        ruiseki[i][j + 1] = ruiseki[i][j] + pow(j, i, MOD)
        ruiseki[i][j + 1] %= MOD
  
for i in range(n):
    for all_num in range(c + 1):
        for j in range(all_num + 1):
            # i番目の子供に、j個の飴を配る
            dp[i+1][all_num] += (ruiseki[j][b[i]+1] - ruiseki[j][a[i]]) * dp[i][all_num - j]
            dp[i+1][all_num] %= MOD
print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
List = list(map(int, input().split()))
ans = 'YES'
for i in range(n - 1):
    for j in range(n - i - 1):
        if List[i] == List[i + j + 1]:
            ans = 'NO'
            break

print(ans)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
Sorted = sorted(List)
ans = 'YES'
for i in range(n - 1):
    if Sorted[i] == Sorted[i + 1]:
        ans = 'NO'
        break

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

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


# [ok, ng) - Maximum
# (ng, ok] - Minimum
# ok が 最終的な答え
ok = N
ng = -1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    n = mid
    dp = [0] * (K + 1)
    dp[0] = 1
    for i in range(N):
        a = 0 if i == n else A[i]
        for j in range(K, -1, -1):
            dp[min(K, j + a)] |= dp[j]
    rst = any(dp[k] for k in range(max(0, K - A[n]), K))
    if rst:
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()


    # [ok, ng) - Maximum
    # (ng, ok] - Minimum
    # ok が 最終的な答え
    ok = N
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        n = mid
        dp = [0] * (K + 1)
        dp[0] = 1
        for i in range(N):
            a = A[i]
            if i == n or a >= K:
                continue
            for j in range(K, -1, -1):
                dp[min(K, j + a)] |= dp[j]
        rst = any(dp[k] for k in range(max(0, K - A[n]), K))
        if rst:
            ok = mid
        else:
            ng = mid
    print(ok)


main()
### BUGGY CODE ###

def stdinput():
    from sys import stdin
    return stdin.readline().strip()

def main():
    n = int(stdinput())
    *A, = map(int, stdinput().split(' '))
    o = mergeSort(A, 0, n)

    print(*A)
    print(o)

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]

    cap = max(A) + 1
    L.append(cap)
    R.append(cap)

    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return i + j

def mergeSort(A, left, right):
    o = 0
    if left + 1 < right:
        mid = (left + right) // 2
        o += mergeSort(A, left, mid)
        o += mergeSort(A, mid, right)
        o +=  merge(A, left, mid, right)
    return o

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')


### FIXED CODE ###

from sys import stdin, maxsize


def stdinput():
    return stdin.readline().strip()

def main():
    n = int(stdinput())
    *A, = map(int, stdinput().split(' '))
    o = mergeSort(A, 0, n)

    print(*A)
    print(o)

def merge(A, left, mid, right):
    L = A[left:mid]
    R = A[mid:right]

    cap = maxsize
    L.append(cap)
    R.append(cap)

    i = j = 0
    for k in range(left, right):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
    return i + j

def mergeSort(A, left, right):
    o = 0
    if left + 1 < right:
        mid = (left + right) // 2
        o += mergeSort(A, left, mid)
        o += mergeSort(A, mid, right)
        o +=  merge(A, left, mid, right)
    return o

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')
### BUGGY CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
clis = [[x[1]]*x[0] for x in lis]
clis = [x for y in clis for x in y]
clis.sort(reverse=True)
l = len(clis)
alis.sort()
ans = 0
for x,y in zip(alis,clis):
    if x>=y:
        ans += x
    else:
        ans += y
if n>l:
    ans += sum(alis[l:])
print(ans)


### FIXED CODE ###

n,m = map(int,input().split())
alis = list(map(int,input().split()))
lis = [list(map(int,input().split())) for x in range(m)]
for x in alis:
    lis.append([1,x])
lis.sort(reverse=True,key=lambda x:x[1])
ans = 0
for x in lis:
    (number,point) = x
    if number >= n:
        number = n
        ans += number * point
        #print(n)
        #print(ans,'+=',number,'*',point)
        break
    ans += number * point
    n -= number
    #print(n)
    #print(ans,'+=',number,'*',point)
print(ans)
#print(lis)
### BUGGY CODE ###

#import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

N = int(readline())
tmp = list(map(int,input().split()))
A = []  
[bisect.insort_right(A, x) for x in tmp]
B = list(map(int,readline().rstrip().split()))
#B = []
#[bisect.insort_right(B,x) for x in tmp ]
C = list(map(int,readline().rstrip().split()))
#C = []
#[bisect.insort_right(C,x) for x in tmp]

A.sort()
B.sort()
C.sort()

listb = []
for i , b in enumerate(B[::-1]):
    if i == 0:
        listb.append(N - bisect.bisect_right(C,b))
    else:
        listb.append(N - bisect.bisect_right(C,b) + listb[i-1])

ans = 0
for a in A :
    indexb = bisect.bisect_right(B,a)
    if indexb == N :
        break
    ans += listb[N-1 - indexb]

print(ans)

### FIXED CODE ###

#import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

N = int(readline())
A = list(map(int,input().split()))
#A = []  
#[bisect.insort_right(A, x) for x in tmp]
B= list(map(int,readline().rstrip().split()))
#B = []
#[bisect.insort_right(B,x) for x in tmp ]
C = list(map(int,readline().rstrip().split()))
#C = []
#[bisect.insort_right(C,x) for x in tmp]

A.sort()
C.sort()

ans = 0
for b in B :
    indA = bisect.bisect_left(A,b)
    indC = bisect.bisect_right(C,b)
    ans += indA * (N-indC)

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

from math import factorial

mod = 10**9 + 7

# 組み合わせ　n_C_r
def comb(n,r):
    if not n >= r:
        return 0
    r = min(r,n-r)
    res = 1
    for i in range(n-r+1,n+1):
        res *= i
    for i in range(1,r+1):
        res //= i
    return res

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

def cal(i):
    return comb(K-1,i-1) * comb(N-K+1,i) % mod

for i in range(1,K+1):
    ans = cal(i)
    print(ans)

### FIXED CODE ###

from math import factorial

mod = 10**9 + 7

# 組み合わせ　n_C_r
def comb(n,r):
    if not n >= r:
        return 0
    return factorial(n) // (factorial(n-r)*factorial(r))

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

def cal(i):
    return comb(K-1,i-1) * comb(N-K+1,i) % mod

for i in range(1,K+1):
    ans = cal(i)
    print(ans)
### BUGGY CODE ###

import itertools

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

ans = 0

a_cum = [0] + list(itertools.accumulate(a))
b_cum = [0] + list(itertools.accumulate(b))

for x in range(len(a_cum)):
    for y in range(len(b_cum)):
        if a_cum[x] + b_cum[y] <= k:
            ans = max(ans, x + y)
        else:
            break

print(ans)


### FIXED CODE ###

import itertools
import sys

input = sys.stdin.readline

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

ans = 0
a_cum = [0] + list(itertools.accumulate(a))
b_cum = [0] + list(itertools.accumulate(b))

y = m  # len(b_cum) - 1
for x in range(len(a_cum)):
    if a_cum[x] > k:
        break
    while b_cum[y] > k - a_cum[x]:
        y -= 1
    ans = max(ans, x + y)

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

import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
index = [0]*(N+1)

for k in range(600000):
    today = [True]*(N+1)
    flag = 0
    for j in range(N):
        if not today[j+1]:
            continue
        if index[j+1] >= N-1:
            continue
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if today[opponent]:
                index[opponent] += 1
                index[j+1] += 1
                today[opponent] = False
                today[j+1] = False
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))
index = [0]*(N+1)
ans = -2
for k in range(10000):
    today = set()
    flag = 0
    for j in range(N):
        if j+1 in today:
            continue
        if index[j+1] >= N-1:
            continue
        #print(j, index[j+1])
        opponent = A[j][index[j+1]]
        if A[opponent-1][index[opponent]] == j+1:
            if opponent not in today:
                index[opponent] += 1
                index[j+1] += 1
                today.add(opponent)
                today.add(j+1)
                flag = 1
    if flag == 0:
        if sum(index) == N*(N-1):
            ans = k
            break
        else:
            ans = -1
            break
    #print(index)

if ans == -2:
    print(N*(N-1)//2)
else:
    print(ans)
### BUGGY CODE ###

# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007

l = len(S)
result = 0

a = pow(26, K, m)
u = pow(26, -1, m) * 25 % m
b = 1
for i in range(K + 1):
    # result += pow(26, K - i, m) * mcomb(len(S) - 1 + i, i) * pow(25, i, m)
    result += a * pow(b, -1, m)
    result %= m
    a *= u
    a %= m
    a *= l + i
    a %= m
    b *= i + 1
    b %= m
print(result)


### FIXED CODE ###

# フェルマーの小定理
K = int(input())
S = input()

m = 1000000007


def make_factorial_table(n):
    result = [0] * (n + 1)
    result[0] = 1
    for i in range(1, n + 1):
        result[i] = result[i - 1] * i % m
    return result


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m


fac = make_factorial_table(len(S) + K)

result = 0
for i in range(K + 1):
    result += pow(26, i, m) * mcomb(len(S) - 1 + K - i, len(S) - 1) * pow(25, K - i, m)
    result %= m
print(result)
### BUGGY CODE ###

from itertools import combinations as cc
l = []
n,k = map(int, input().split())
xs,ys = set(),set()
t = 10**24
for _ in range(n):
  x,y = map(int, input().split())
  xs.add(x)
  ys.add(y)
  l.append((x,y))
xs = sorted(list(xs))
ys = sorted(list(ys))
for xl,xr in cc(xs,2):
  for yl,yr in cc(ys,2):
    cnt = 0
    for x,y in l:
      if xl<=x<=xr and yl<=y<=yr:
        cnt += 1
      if cnt >= k:
        s = (xr-xl)*(yr-yl)
        if t > s:
          t = s
print(t)

### FIXED CODE ###

from itertools import combinations as cc
l = []
n,k = map(int, input().split())
xs,ys = set(),set()
t = 10**24
for _ in range(n):
  x,y = map(int, input().split())
  xs.add(x)
  ys.add(y)
  l.append((x,y))
xs = sorted(list(xs))
ys = sorted(list(ys))
for xl,xr in cc(xs,2):
  for yl,yr in cc(ys,2):
    cnt = 0
    for x,y in l:
      if xl<=x<=xr and yl<=y<=yr:
        cnt += 1
      if cnt >= k:
        s = (xr-xl)*(yr-yl)
        if t > s:
          t = s
print(t)
### BUGGY CODE ###

import math
N = int(input())
for i in range(1, N+1):
    cnt = 0
    for x in range(1, int(math.pow(i, 1.0/2.5)+1)):
        for y in range(1, int(math.pow(i, 1.0/2.5)+1)):
            for z in range(1, int(math.pow(i, 1.0/2.5)+1)):
                if ((x+y+z)**2)-x*y-y*z-z*x == i:
                    cnt += 1
    print(cnt)

### FIXED CODE ###

N = int(input())
lis = [0]*N
for x in range(1, 100):
    for y in range(1, 100):
        for z in range(1, 100):
            ans = x**2 + y**2 + z**2 + x*y + y*z + z*x -1
            if ans >= N:
                pass
            else:
                lis[ans] += 1
for i in range(N):
    print(lis[i])
### BUGGY CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

# まずは赤と緑の中だけで最大となるようX+Y個のりんごを選ぶ．
p_x = sorted(p, reverse=True)[:x].copy()
q_y = sorted(q, reverse=True)[:y].copy()
eats = p_x + q_y
i, j = 0, 0
while r and max(r) >= min(eats):
    mi = min(eats)
    eats[eats.index(mi)] = max(r)
    r.remove(max(r))

print(sum(eats))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

eats = sorted(p, reverse=True)[:x] + sorted(q, reverse=True)[:y] + r
eats.sort(reverse=True)
print(sum(eats[:x+y]))
### BUGGY CODE ###

import numpy as np

N, Q = map(int, input().split())  # 複数数値入力
S = list(input())  # 一文字ずつ格納
L = []
R = []

for i in range(Q):
    l, r = map(int, input().split())  # 複数数値入力
    L.append(l)
    R.append(r)

list = []
flg = 0
for s in S:
    if s == "A" and flg == 0:
        flg = 1
    elif s == "C" and flg == 1:
        list.append(1)
        list.append(2)
        flg = 0
    elif flg == 1:
        list.append(0)
        list.append(0)
    else:
        list.append(0)

for i in range(Q):
    S = list[L[i] - 1:]
    S = S[:R[i] - L[i] + 1]
    if S[0] == 2:
        S = S[1:]
    if S[-1] == 1:
        S = S[:-2]

    S = np.array(S)
    print(int(np.sum(S)/3))


### FIXED CODE ###

import numpy as np

N, Q = map(int, input().split())  # 複数数値入力
S = list(input())  # 一文字ずつ格納

dp = [0] * N
i = 0
flg = False
for str in S:
    if str == "C" and flg == True:
        dp[i] = dp[i - 1] + 1
        flg = False
    elif str == "A":
        flg = True
        dp[i] = dp[i-1]
    else:
        flg = False
        dp[i] = dp[i-1]
    i += 1

for i in range(Q):
    l, r = map(int, input().split())  # 複数数値入力
    print(dp[r-1]-dp[l-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n < 2:
    return []
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  while True:
    p = data[0]
    if limit <= p:
      return prime + data
    prime.append(p)
    data = [e for e in data if e%p != 0]
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
data = prime_table(max(a))
prime = [0] * len(data)
l_prime = []
for i in a:
  for j in range(len(data)):
    c = 0
    while True:
      if i % data[j] == 0:
        i = i // data[j]
        c += 1
      else:
        break
    prime[j] = max(prime[j],c)
    if i == 1:
      break
  if i != 1:
    l_prime.append(i)
lcm = 1
for i,j in zip(data,prime):
  lcm = (lcm*pow(i,j,MOD))%MOD
for i in l_prime:
  lcm = (lcm*i) % MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)

### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n <= 1:
    return [],[],[]
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  isprime = [0]*(n+1)
  isprime[2] = 1
  min_factor = [0 if i%2 != 0 else 2 for i in range(n+1)]
  while True:
    p = data[0]
    prime.append(p)
    isprime[p] = 1
    pdata,data = data,[]
    for e in pdata:
      if e%p != 0:
        data.append(e)
      else:
        min_factor[e] = p
    if limit <= p:
      for i in data:
        isprime[i] = 1
        min_factor[i] = i
      return prime + data,isprime,min_factor
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
ma = max(a)
data,isprime,min_factor = prime_table(ma)
prime = [0] * (ma+1)
for i in a:
  if i == 1:
    continue
  d = defaultdict(int)
  while isprime[i] == 0:
    d[min_factor[i]] += 1
    i = i // min_factor[i]
  d[i] += 1
  for j,k in d.items():
    prime[j] = max(prime[j],k)
lcm = 1
for i in range(ma+1):
  if prime[i] != 0:
    lcm = (lcm*pow(i,prime[i],MOD))%MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
L = []
for i in range(M):
	b, c = map(int, input().split())
	_ = [c, b]
	L.append(_)
	L.sort()
	L.reverse()
x = 0
while len(A) > L[0][1]:
	for i in range(L[0][1]):
		x += max(A[0], L[0][0])
		del A[0]
	del L[0]
	if L == []:
		break
if L == []:
	x += sum(A)
else:
	for i in A:
		x += max(i, L[0][0])
print(x)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
L = []
for i in range(M):
	b, c = map(int, input().split())
	L.append((c, b))
L = sorted(L, reverse = True)
L.append((0, N))
temp = 0
sum = 0
for i in range(M + 1):
	for j in range(L[i][1]):
		if A[temp] < L[i][0]:
			sum += L[i][0]
			temp += 1
		else:
			sum += A[temp]
			temp += 1
		if temp == N:
			break
	if temp == N:
		break
print(sum)
### BUGGY CODE ###

import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.append(i)
        I.sort()
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect


def main():
    N = int(input())
    P = list(map(int, input().split(' ')))
    Q = [0] + P + [N + 1]
    index_q = [0 for _ in range(len(Q))]
    for i, q in enumerate(Q):
        index_q[q] = i
    I = [0, 0, N + 1, N + 1]
    ans = 0
    for c in range(N, 0, -1):
        i = index_q[c]
        j = bisect.bisect_left(I, i)
        w, x, y, z = I[j - 2], I[j - 1], I[j], I[j + 1]
        ans += c * ((x - w) * (y - i) + (i - x) * (z - y))
        I.insert(j, i)
    print(ans)


if __name__ == '__main__':
    main()