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

def saidaikouyaku(a, b):
    if b > a:
        a, b = b, a

    while b != 0:
        a, b=b,a%b
    return a

A, B, C, D = map(int, input().split())
hani = B - A + 1
count = 0
count2 = 0
count3 = 0
saisyoukoubai = int(C * D / saidaikouyaku(C, D))
for i in range(A, B + 1):
    if i % C == 0:
        count += 1
    if i %  D == 0:
        count2 += 1
    if i % saisyoukoubai == 0:
        count3 += 1

print(hani - count - count2 + count3)



### FIXED CODE ###

def saidaikouyaku(a, b):
    if b > a:
        a, b = b, a

    while b != 0:
        a, b=b,(a%b)
    return a

A, B, C, D = map(int, input().split())
hani = B - A + 1
Cnum = B // C - (A - 1) // C
Dnum = B // D - (A - 1) // D
saisyoukoubai = C * D // saidaikouyaku(C, D)
koubainum = B // saisyoukoubai - int(A - 1) // saisyoukoubai
#print(hani)
#print(Cnum, Dnum, koubainum, saisyoukoubai)
print(hani - Cnum - Dnum + koubainum)
### BUGGY CODE ###

count = int(input())
nums = input().split(" ")

product = 1

if ("0" in nums):
    print(0)
else:
    for i in nums:
        product *= int(i)
    if (product > 10**18):
        print(-1)
    else:
        print(product)

### FIXED CODE ###

count = int(input())
nums = input().split(" ")

product = 1

if ("0" in nums):
    print(0)
else:
    for i in nums:
        product *= int(i)
        if (product > 10**18):
            print(-1)
            exit()
    print(product)
### BUGGY CODE ###

import heapq

N,M = map(int,(input().split()))
A = [0]*N
B = [0]*N
mission = [[] for _ in range(M+1)]
work = 0

for i in range(N):
    if i <= M:
        heapq.heapify(mission[i])
    A[i],B[i] = map(int,(input().split()))
    if A[i] <= M:
        mission[A[i]].append(-B[i])

for day in range(1,M+1):
    mission[day].extend(mission[day-1])
    if mission[day]:
        heapq.heapify(mission[day])
        work += heapq.heappop(mission[day])

print(-work)

### FIXED CODE ###

import heapq

N,M = map(int,(input().split()))
A = [0]*N
B = [0]*N
mission = [[] for _ in range(M+1)]
work = 0

for i in range(N):
    if i <= M:
        heapq.heapify(mission[i])
    A[i],B[i] = map(int,(input().split()))
    if A[i] <= M:
        mission[A[i]].append(-B[i])

for day in range(1,M+1):
    for i in range(len(mission[day])):
        heapq.heappush(mission[0],mission[day][i])
    if mission[0]:
        work += heapq.heappop(mission[0])

print(-work)
### BUGGY CODE ###

x = int(input())

for i in range(1, int(x**0.5)+1):
  if x%i==0:
    y = i
    z = x//i
    
    a = 1
    ans = False
    
    while True:
      if a**5-(a-y)**5==x:
        ans = True
        b = a-y
        break
      if a**5-(a-z)**5==x:
        ans = True
        b = a-z
        break
      if a^5-(a-z)^5>x and a^5-(a-z)^5>x:
        break
      a += 1
    
    if ans:
      break
      
print(a, b)

### FIXED CODE ###

x = int(input())
found = False
a = 0
b = 0

for i in range(-200, 201):
  for j in range(-200, 201):
    if i**5-j**5==x:
      found = True
      a = i
      b = j
  if found:
    break
    
print(a, b)
### BUGGY CODE ###

import random

D = int(input())
C = [*map(int, input().split())]
S = [[*map(int, input().split())] for _ in range(D)]

O = [[0]*26 for _ in range(D)]
A = [[0]*26 for _ in range(D)]

def last(d,t):
    for i in range(d,-1,-1):
        if O[i][t] > 0: return i
    return 0

T = []
t = 0
for d in range(D):
    t = int(random.uniform(1,27))
    T.append(t)

# print(*T,sep='\n')

score = 0
t = 0
for d in range(D):
    t = T[d] - 1
    O[d][t] = 1
    dw = 0
    for i in range(26):
        dw += C[i]*((d+1) - last(d,i))
    A[d][t] = S[d][t] - dw
    score += A[d][t]
# print(score)

for _ in range(100000):

    TT = []
    for d in range(D):
        t = int(random.uniform(1,27))
        TT.append(t)

    now = 0
    t = 0
    for d in range(D):
        t = TT[d] - 1
        O[d][t] = 1
        dw = 0
        for i in range(26):
            dw += C[i]*((d+1) - last(d,i))
        A[d][t] = S[d][t] - dw
        now += A[d][t]
    if score < now:
        score = now
        T = TT

# print(score)

print(*T,sep='\n')


### FIXED CODE ###

D = int(input())
C = [*map(int, input().split())]
S = [[*map(int, input().split())] for _ in range(D)]

# print(D)
# print(C)
# print(*S,sep='\n')

O = [[0]*26 for _ in range(D)]
A = [[0]*26 for _ in range(D)]

def last(d,t):
    for i in range(d,-1,-1):
        if O[i][t] > 0: return i
    return 0

score = 0
t = 0
for d in range(D):
    O[d][t] = 1
    dw = 0
    for i in range(26):
        dw += C[t]*(d - last(d,i))
    A[d][t] = S[d][t] - dw
    score += A[d][t]
    print(t+1)
    t = (t+1) % 26
# print(score)

# t = 0
# for d in range(D):
#     O[d][t] = 1
#     dw = 0
#     for i in range(26):
#         dw += C[t]*(d - last(d,i))
#     A[d][t] = S[d][t] - dw
#     print(t)
#     t = (t+1) % 26

# for d in range(D):
#     s = 0
#     for t in range(26):
#         s += C[t]*(d - last(d,t))
#     print(s)
### BUGGY CODE ###

import numpy as np
N,M = list(map(int,input().split()))
A = input().split()
 
count = 0
A = np.array(A,dtype='int64')
B = np.cumsum(A)
C = np.append([0],B)
 
L = [1 for i in C for t in C if i<t and (t - i)%M==0]
print(len(L))

### FIXED CODE ###

import collections
import numpy as np

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

A = np.array(A,dtype='int64')
C = np.append([0],np.cumsum(A))
L = [i%M for i in C]
L_c = collections.Counter(L)

ans = 0
for i in L_c.values():
    S = i * (i-1) / 2
    ans+=S
    
print(int(ans))
### BUGGY CODE ###

import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

def main():
    N, X, Y = map(int, input().split())

    ans = [0] * N
    for i in range(1, N+1):
        dist = [-1] * (N+1)
        dist[i] = 0
        q = deque()
        q.append(i)
        def push(l, m):
            if dist[l] > -1:
                return
            q.append(l)
            dist[l] = dist[m] + 1
            ans[dist[l]] += 1

        while q:
            j = q.popleft()
            if j < N: push(j+1, j)
            if j > 1: push(j-1, j)
            if j == X: push(Y, j)
            if j == Y: push(X, j)
    for i in range(1, N):
        print(ans[i]// 2)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, X, Y = map(int, input().split())

    ans = [0] * N
    for i in range(1, N):
        for j in range(i+1, N+1):
            if i >= Y or j <= X:
                ans[j-i] += 1
            else:
                ans[min(j-i, abs(X-i) + abs(Y-j)+1)] += 1
    print(*ans[1:], sep='\n')

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

#!/usr/bin/env python3
n, *A = map(int, open(0).read().split())
c = 0
A.sort(reverse=1)
s = set()
for i, a in enumerate(A):
    c += a not in s and all(a%j for j in A[i+1:])
    s.add(a)
print(c)

### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter
n, *A = map(int, open(0).read().split())
A.sort()
c, s = Counter(A), set()
M = max(A) + 1
ans = 0
for a in A:
    if a in s:
        continue
    ans += c[a] == 1
    for i in range(a, M, a):
        s.add(i)
print(ans)
### BUGGY CODE ###

import heapq

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

for i in range(M):
    B,C = map(int,input().split())
    D = [C]* B
    A = A + D
    
A.sort()
print(sum(A[-N:]))

### FIXED CODE ###

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

L = []
for i in range(M):
    bc = tuple(map(int,input().split()))
    L.append(bc)

L = sorted(L,key=lambda x:-x[1])
n = 0
for b,c in L:
    n += b
    A += [c] * b
    if n >= N:
        break
        
A.sort()
print(sum(A[-N:]))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = float("inf")
s = sum(a)
for i in range(1,n):
  if ans > abs(sum(a[:i])*2 - s):
    ans = abs(sum(a[:i])*2 - s)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = sum(a)
d = [s - a[0]*2,] + [0 for _ in range(n-2)]
for i in range(1,n-1):
    d[i] = d[i-1] - a[i]*2
print(min([abs(i) for i in d]))
### BUGGY CODE ###

import itertools
import collections

N=int(input())
S=list(input())
answer=0
col = collections.Counter(S)
values, counts = zip(*col.most_common())

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer+=sum(kumiawase)
print(answer%(7+10**9))

### FIXED CODE ###

N=list(range(int(input())))
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0

for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(1+counter)
        counter=1
if counter!=0:
    counts.append(1+counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

answer=soujou(counts)-1
print(answer%(7+10**9))
### BUGGY CODE ###

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

prev = 0
for i in range(0,n-1):
    left = list[:i+1]
    right = list[i+1:]
    diff = abs(sum(left) - sum(right))
    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)


### FIXED CODE ###

n = int(input())
array = list(map(int,input().split(' ')))

left= array[0]
right = sum(array) - left

prev = 0
for i in range(0,n-1):
    diff = abs(left - right)
    left = left + array[i+1]
    right = right - array[i+1]

    if(i == 0):
        prev = diff
    else:
        if diff < prev:
            prev = diff
print(prev)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    # print(ab)
    bridge = [True] * (N-1)
    count = 0
    for a, b in ab:
        a -= 1; b -= 1;
        ok = True
        for i in range(a, b):
            if not bridge[i]:
                ok = False
                break
        if ok:
            bridge[b-1] = False
            count += 1
    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    count = 0
    break_ = -1
    for a, b in ab:
        a -= 1; b -= 1;
        if a > break_:
            count += 1
            break_ = b-1
    print(count)

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

N = int(input())
ll = list(map(int, input().split(" ")))


def ni(i):
    return int(bin(i)[2:])


for i in range(N):
    ll[i] = ni(ll[i])

count = N
s = N
for i in range(N):
    s = ll[i]

    for j in range(i+1, N):
        s = s + ll[j]
        if "2" in str(s):
            break
        else:
            count += 1
print(count)




### FIXED CODE ###

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

l, r = 0, 0
sum_a = 0
ans = 0
while r < n:
    # 右端を進める
    if sum_a & a[r] == 0:
        sum_a += a[r]
        r += 1
        ans += r - l
    # 右端と左端を進める
    elif l == r:
        l += 1
        r += 1
    # 左端を進める
    else:
        sum_a -= a[l]
        l += 1
    # print('l={}, r={}, size={}, ans={}, {}'.format(l, r, r - l, ans, a[l:r]))
print(ans)
### BUGGY CODE ###

A=list(map(int,input().split()))
t=True
C=2019
if (A[1]-A[0])<2019:
    for i in range(A[1]):
        for t in range(A[1]+1):
            if t>i and i>=A[0]:
                if t*i%2019<C:
                        C=t*i%2019
else:
    C=0
print(C)

### FIXED CODE ###

l,r=list(map(int,input().split()))
f=True
C=2019
if (r-l)<2019:
    for i in range(l,r+1):
        if C==0:
            break
        for t in range(i+1,r+1):
            if t*i%2019<C:
                C=t*i%2019
                if C==0:
                    break
else:
    C=0
print(C)
### BUGGY CODE ###

N = int(input())
A = []
for i in range(0, N):
  A.append(int(input()))

for j in range(0, N):
  list = A[:j] + A[j+1:]
  print(max(list))

### FIXED CODE ###

N = int(input())
max_1st = -1
max_1st_index = -1
max_2nd = -1
only_max = False
for i in range(0, N):
  if i == 0:
    max_1st = int(input())
    max_1st_index = 0
  elif i == 1:
    tmp = int(input())
    if (tmp > max_1st):
      max_1st, max_2nd = tmp, max_1st
      max_1st_index = 1
    else:
      max_2nd = tmp
  else:
    tmp = int(input())
    if (max_2nd < tmp) and (tmp < max_1st):
      max_2nd = tmp
    elif (max_1st < tmp):
      max_1st, max_1st_index = tmp, i
      only_max = False
    elif (max_1st == tmp):
      only_max = True

for j in range(0, N):
  if only_max:
    print(max_1st)
  else:
    if j == max_1st_index:
      print(max_2nd)
    else:
      print(max_1st)
### BUGGY CODE ###

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

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

dp = np.zeros([N+1,W+1],dtype=int)

for i in range(N):
    weight,value = map(int, input().split())
    for sum_w in range(W+1):
        if sum_w - weight >=  0:
            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - weight] + value)
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[N][W])


### FIXED CODE ###

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

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

dp = np.zeros([N+1,W+1],dtype=int)

# 重かったので却下
# for i in range(N):
#     weight,value = map(int, input().split())
#     for sum_w in range(W+1):
#         if sum_w - weight >=  0:
#             dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - weight] + value)
#         dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

for i in range(N):
    weight, value = map(int, input().split())
    dp[i+1] = dp[i]
    dp[i+1, weight:] = np.maximum(dp[i+1, weight:], dp[i, :W-weight+1] + value)

print(dp[N][W])
### BUGGY CODE ###

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

lists = []
for i in range(1,len(A)+1):
    lists.append(A.index(i)+1)
         
for i in lists:
         print(i, end = ' ')

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
lists = [0] * n

for i in range(n):
    lists[a[i] - 1] = i + 1
    
for i in lists:
  print(i , end =' ')
### BUGGY CODE ###

from collections import deque

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

seen = [0] * N
q = deque()
group = []

for i in range(N):
    if seen[i]:
        continue
    q.append(i)
    seen[i] = 1
    k = 1
    while q:
        t = q.popleft()
        for j in range(M):
            if AB[j][0] == i + 1 and seen[AB[j][1] - 1] != 1:
                q.append(AB[j][1])
                seen[AB[j][1] - 1] = 1
                k += 1
            if AB[j][1] == i + 1 and seen[AB[j][0] - 1] != 1:
                q.append(AB[j][0] - 1)
                seen[AB[j][0] - 1] = 1
                k += 1
    group.append(k)

print(max(group))


### FIXED CODE ###

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

class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):  # 要素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が属するグループと要素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 same(self, x, y):  # 要素x, yが同じグループに属するかどうかを返す
        return self.find(x) == self.find(y)

    def size(self, x):  # 要素xが属するグループのサイズ（要素数）を返す
        return -self.parents[self.find(x)]

    def members(self, x):  # 要素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())


uf = UnionFind(N)
for i in range(M):
    uf.union(AB[i][0] - 1, AB[i][1] - 1)
l = []
for i in range(N):
    l.append(uf.size(i))
print(max(l))
### BUGGY CODE ###

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

dup=[0]*n
for num in a:
    dup[num-1]+=1
    if dup[num-1]>1:
        break

A=-1
B=-1
for i in range(len(a)):
    if a[i]==num:
        if A==-1:
            A=i
        else:
            B=i
B=n-B
def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist

def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
NUM = (10**5)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)
def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)

print(n)
for k in range(2,n+2):
    base=comb(n+1,k)
    for i in range(k):
        j=k-i-1
        base-= comb(A,i) *comb(B,j)

    print(base)


### FIXED CODE ###

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

dup=[0]*n
for num in a:
    dup[num-1]+=1
    if dup[num-1]>1:
        break

A=-1
B=-1
for i in range(len(a)):
    if a[i]==num:
        if A==-1:
            A=i
        else:
            B=i
B=n-B

def find_power(n,mod=10**9+7):
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
  
def find_inv_power(n,mod=10**9+7):
    powlist=find_power(n)
    check=powlist[-1]
    first=1
    uselist=[0]*(n+1)
    secondlist=[0]*30
    secondlist[0]=check
    secondlist[1]=check**2
    for i in range(28):
        secondlist[i+2]=(secondlist[i+1]**2)%(10**9+7)
    a=format(10**9+5,"b")
    for j in range(30):
        if a[29-j]=="1":
            first=(first*secondlist[j])%(10**9+7)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(10**9+7)
    return uselist

mod = 10**9+7
NUM = (10**5)+100
p_lis=find_power(NUM,mod)
ip_lis=find_inv_power(NUM,mod)

def comb(n,r,mod=10**9+7):
    if n<r:
        return 0
    elif n>=r:
        return (p_lis[n]*ip_lis[r]*ip_lis[n-r])%(mod)

print(n)
for k in range(2,n+2):
    base=comb(n+1,k) - comb(A+B,k-1)

    print(base%mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(list(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase.append(a)
Abase2=[]
for _ in range(N):
    Abase2=Abase2+Abase
A=set(itertools.combinations(Abase2,N))
A=list(A)
A2=[sorted(x) for x in A]
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j : i for i, j in enumerate(path)}
already = set()
dis_dict = {i : 0 for i in range(n)}
stack = [(u, 0, 0)]
while len(stack) > 0:
    ind, cur_dis, minus = stack.pop(-1)
    already.add(ind)
    dis_dict[ind] = cur_dis - minus
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis + 1:
                continue
            else:
                stack.append((_next, cur_dis + 1, minus + 2))
        else:
            stack.append((_next, cur_dis + 1, minus))

res = max(dis_dict.values())


if res == 0:
    print(distance - 1)
else:
    print(distance + res - 1)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i: [] for i in range(n)}
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j: i for i, j in enumerate(path)}
already = set()
ls = []
stack = [(u, 0, 0)]
while len(stack) > 0:
    ind, cur_dis, minus = stack.pop(-1)
    already.add(ind)
    ls.append(cur_dis - minus)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis + 1:
                continue
            else:
                stack.append((_next, cur_dis + 1, minus + 2))
        else:
            stack.append((_next, cur_dis + 1, minus))

res = max(ls)

if res == 0:
    print(distance - 1)
else:
    print(distance + res - 1)
### BUGGY CODE ###

n = int(input())
ListP =[int(i) for i in input().split()]
points = 0
ListPos2 = [0] * (n + 1)
for i, a in enumerate(ListP):
	ListPos2[a] = i + 1
ListPos = [0, 0] + [ListPos2[n]] + [n+1, n+1]
area = list(reversed(range(1,n)))
for i in area:
	ListPos.append(ListPos2[i])
	ListPos.sort()
	pos = ListPos.index(ListPos2[i])
	lh = ListPos[pos]
	l1 = ListPos[pos-1]
	l2 = ListPos[pos-2]
	h1 = ListPos[pos+1]
	h2 = ListPos[pos+2]
	points += i * ((lh-l1)*(h2-h1) + (h1-lh)*(l1-l2))
	#low1 = ListPos[pos] - ListPos[pos-1]
	#low2 = ListPos[pos-1] - ListPos[pos-2]
	#high1 = ListPos[pos+1] - ListPos[pos]
	#high2 = ListPos[pos+2] - ListPos[pos+1]
	#points += i * (low1 * high2 + high1 * low2)
	#print(i, ListPos)
	#print(points, low1, high2, high1, low2)
print(points)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

pos_list = [0] * n
for ind, i in enumerate(p):
	pos_list[i-1] = ind

left_nextInd = list(range(-1, n-1)) + [-1, -1]
right_nextInd = list(range(1, n+1)) + [n, n]

answer = 0
for i in range(1, n):
	ind = pos_list[i-1]
	l1 = left_nextInd[ind]
	l2 = left_nextInd[l1]
	r1 = right_nextInd[ind]
	r2 = right_nextInd[r1]

	answer += i * ((ind-l1) * (r2-r1) + (r1-ind) * (l1-l2))

	left_nextInd[r1] = l1
	right_nextInd[l1] = r1
print(answer)