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

from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["#"*(w+4)]
s.append("#"*(w+4))
for _ in range(h):
    s.append("##" + input() + "##")
s.append("#"*(w+4))
s.append("#"*(w+4))

ans = [[-1]*(w+4) for _ in range(h+4)]
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
            ans[i][j] = -2
ans[start_h][start_w] = 0

move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),(-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),(0, -2), (0, -1), (0, 0), (0, 1), (0, 2),(1, -2), (1, -1), (1, 0), (1, 1), (1, 2),(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

yet = deque([(start_h, start_w)])
done = deque()

while len(yet) > 0:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: #"."でまだ辿り着いていないマス
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while len(done) > 0:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])


### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
start_h, start_w = map(int, input().split())
goal_h, goal_w = map(int, input().split())

start_h += 1
start_w += 1
goal_h += 1
goal_w += 1

s = ["#"*(w+4)]
s.append("#"*(w+4))
for _ in range(h):
    s.append("##" + input() + "##")
s.append("#"*(w+4))
s.append("#"*(w+4))

ans = [[-1]*(w+4) for _ in range(h+4)]
for i in range(h+4):
    for j in range(w+4):
        if s[i][j] == "#":
            ans[i][j] = -2
ans[start_h][start_w] = 0

move1 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),(-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),(0, -2), (0, -1), (0, 0), (0, 1), (0, 2),(1, -2), (1, -1), (1, 0), (1, 1), (1, 2),(2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]

yet = deque([(start_h, start_w)])
done = deque()

while len(yet) > 0:
    x1, y1 = yet.popleft()
    done.append((x1, y1))
    for (p, q) in move1:
        v1, v2 = x1+p, y1+q
        if ans[v1][v2] == -1: #"."でまだ辿り着いていないマス
            yet.append((v1, v2))
            ans[v1][v2] = ans[x1][y1]

    if len(yet) == 0:
        while len(done) > 0:
            x2, y2 = done.popleft()
            for (p, q) in move2:
                i, j = x2+p, y2+q
                if ans[i][j] == -1:
                    ans[i][j] = ans[x2][y2]+1
                    yet.append((i, j))

print(ans[goal_h][goal_w])
### BUGGY CODE ###

INF = float('inf')

N, K = map(int, input().split())
h = list(map(int, input().split()))
h = [0] + h

dp = [INF for i in range(N + 1)]
# 1-indexed, 1 -> N
dp[1] = 0

for i in range(2, N + 1):
    dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    for j in range(2, K + 1):
        if i - j >= 1:
            dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]))
print(dp[N])


### FIXED CODE ###

INF = 10 ** 10

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

dp = [INF for _ in range(N)]
dp[0] = 0
# 0-indexed

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

print(dp[N - 1])
### BUGGY CODE ###

s = input()
q = int(input())
inv = 1
for i in range(q):
  t = input()
  if t[0] == '1':
    inv *= -1 #s = s[::-1]
  else:
    _, f, c = map(str, t.split())
    if (f =='1' and inv == 1) or (f =='2' and inv == -1):
      s = c+s
    else:
      s = s+c

print(s[::inv])

### FIXED CODE ###

s = list(input())
q = int(input()) #int(input())
inv = 1
query = [input() for _ in range(q)]
bef = []
aft = []


for t in query:
  if t == '1':
    inv *= -1 #s = s[::-1]
  else:
    _, f, c = map(str, t.split())
    if (f =='1' and inv == 1) or (f =='2' and inv == -1):
      # s = c+s
      bef.append(c)
    else:
      # s = s+c
      aft.append(c)

bef.reverse()
bef.extend(s)
bef.extend(aft)

print(''.join(bef[::inv]))
### BUGGY CODE ###

mod=10**9+7
 
def framod(n, mod, a=1):
  for i in range(1,n+1):
    a=a * i % mod
  return a
  
def power(n, r, mod):
  if r == 0: return 1
  if r%2 == 0:
    return power(n*n % mod, r//2, mod) % mod
  if r%2 == 1:
    return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
  a=framod(n, mod)
  b=framod(k, mod)
  c=framod(n-k, mod)
  return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

N, K=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
ans=0
for i in range(N-K+1):
  n, r=N-i-1, K-1
  ans=(ans+(A[-(i+1)]-A[i])*comb(n, r, mod)%mod)%mod
print(ans)


### FIXED CODE ###

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

mod=10**9+7
N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

N, K=map(int, input().split())
A=list(map(int, input().split()))
A.sort()
ans=0
for i in range(N-K+1):
  n, r=N-i-1, K-1
  ans=(ans+(A[-(i+1)]-A[i])*comb(n, r, mod)%mod)%mod
print(ans)
### BUGGY CODE ###

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

N = int(input())
L = np.sort(np.array(list(map(int, input().split()))))

ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        t = np.count_nonzero(L[j + 1:] < L[i] + L[j])
        ans += t

print(ans)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = index - j - 1
        ans += n

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

from collections import Counter
H, W, N = map(int, raw_input().split(' '))

T = Counter()

for _ in range(N):
    x, y = map(int, raw_input().split(' '))
    x -= 1
    y -= 1
    T[(x, y + 1)] += 1
    T[(x, y)] += 1
    T[(x, y - 1)] += 1
    T[(x-1,y+1)] += 1
    T[(x-1,y)] += 1
    T[(x-1,y-1)] += 1
    T[(x + 1, y + 1)] += 1
    T[(x + 1, y)] += 1
    T[(x + 1, y - 1)] += 1

ans = [0] * 10
total_points = H * W - (2 * H) - (2 * (W-2))
positive_points = 0
for (x, y), c in T.iteritems():
    if 0 < x < H-1 and 0 < y < W-1:
        ans[c] += 1
        positive_points += 1
ans[0] = total_points - positive_points

for i in range(10):
    print ans[i]

### FIXED CODE ###

from collections import Counter
H, W, N = map(int, raw_input().split(' '))

T = Counter()

for _ in range(N):
    x, y = map(lambda _x: int(_x) - 1, raw_input().split(' '))
    T[(x, y + 1)] += 1
    T[(x, y)] += 1
    T[(x, y - 1)] += 1
    T[(x-1,y+1)] += 1
    T[(x-1,y)] += 1
    T[(x-1,y-1)] += 1
    T[(x + 1, y + 1)] += 1
    T[(x + 1, y)] += 1
    T[(x + 1, y - 1)] += 1

ans = [0] * 10
total_points = H * W - (2 * H) - (2 * (W-2))
positive_points = 0
for (x, y), c in T.iteritems():
    if 0 < x < H-1 and 0 < y < W-1:
        ans[c] += 1
        positive_points += 1
ans[0] = total_points - positive_points

for i in range(10):
    print ans[i]
### BUGGY CODE ###

a,v = map(int, input().split())
b,w = map(int, input().split())
T = int(input())
if v == w:
  print("NO")
  exit()

for i in range(0,T+1):
  if a == b:
    print("YES")
    exit()
  else:
    if a < b:
      a = a+v
      b = b+w
    else:
      a = a-v
      b = b-w
    
print("NO")

### FIXED CODE ###

a,v = map(int,input().split())
b,w = map(int,input().split())
T = int(input())
if abs((b-a))<=(v-w)*T:
	print("YES")
else:
	print("NO")
### BUGGY CODE ###

N = int(input())
p = set()
for _ in range(N):
    x, y = map(int, input().split())
    if (x, y) not in p:
        p.add((x, y))
p = list(p)

def cross(a, b, c, d):
    return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])


def convex_hull(ps):
    qs = []
    n = len(ps)
    for p in ps:
        while len(qs) > 1 and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    t = len(qs)
    for i in range(n-2, -1, -1):
        p = ps[i]
        while len(qs) > t and cross(qs[-1], qs[-2], qs[-1], p) >= 0:
            qs.pop()
        qs.append(p)
    return qs


def dist(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


def rotating_calipers(ps):
    qs = convex_hull(ps)
    n = len(qs)
    if n == 2:
        return dist(qs[0], qs[1])
    i = j = 0
    for k in range(n):
        if qs[k] < qs[i]: i = k
        if qs[j] < qs[k]: j = k
    res = 0
    si = i; sj = j
    while i != sj or j != si:
        res = max(res, dist(qs[i], qs[j]))
        if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
            i = (i + 1) % n
        else:
            j = (j + 1) % n
    return res


print(rotating_calipers(p))

### FIXED CODE ###

N = int(input())
p = []
for _ in range(N):
    x, y = map(int, input().split())
    p.append((x, y))
p = sorted(p, key=lambda i: i[0] + i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
res = abs((x1 + y1) - (x2 + y2))
p = sorted(p, key=lambda i: i[0] - i[1])
x1, y1 = p[0]
x2, y2 = p[-1]
res = max(abs((x1 - y1) - (x2 - y2)), res)
print(res)
### BUGGY CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []

for i in range(M):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

heapq.heapify(A)

for i, b in enumerate(B):
    for j in range(b):
        min_a = heapq.heappop(A)
        if min_a >= C[i]:
            heapq.heappush(A, min_a)
            break
        else:
            min_a = C[i]
        heapq.heappush(A, min_a)

print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []
BC = []

for i in range(M):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)
    BC.append([b, c])

BC.sort(reverse=True, key=lambda x: x[1])

heapq.heapify(A)

flag = True
for bc in BC:
    for j in range(bc[0]):
        min_a = heapq.heappop(A)
        if min_a >= bc[1]:
            heapq.heappush(A, min_a)
            flag = False
            break
        else:
            min_a = bc[1]
        heapq.heappush(A, min_a)
    if not flag:
        break

print(sum(A))
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]
b = [0]
for i in range(n):
    b.append(a[i] + b[i])
s = set(b)
ans = 0
for i in s:
    x = b.count(i)
    ans += x * (x-1) /2
print(int(ans))

### FIXED CODE ###

import numpy as np
from collections import Counter

n = int(input())
a = [0]+[int(x) for x in input().split()]

b = np.cumsum(a)
count = Counter(b)
ans = 0
for i in count.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

N=int(input())
A=list(input().split())
ans='YES'
for i in range(N):
  if A.count(A[i])>=2:
    ans='NO'
    break
print(ans)

### FIXED CODE ###

N=int(input())
A=list(input().split())
B=list(set(A))
ans='YES'
if len(A)!=len(B):
  ans='NO'   
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, K = MAP()
S = input()

def searchRL(S):
    ans = []
    for i in range(N-1):
        if S[i] == "R" and S[i+1] == "L":
            ans.append(i)
    return ans

def searchLR(S):
    ans = []
    for i in range(N-2,-1,-1):
        if S[i] == "L" and S[i+1] == "R":
            ans.append(i)
    return ans

def reverse(S):
    S = list(S)
    for i in range(len(S)):
        if S[i] == 'L':
            S[i] = 'R'
        if S[i] == 'R':
            S[i] = 'L'
    return ''.join(S)


def solve(S):
    RL = searchRL(S)
    LR = searchLR(S)
    if len(RL) == 0 and len(LR) == 0:
        return S, 0
    if len(RL) == 0:
        S = reverse(S[LR[0]::-1]) + S[LR[0]+1:]
        return S, 1
    if len(LR) == 0:
        S = reverse(S[RL[0]::-1]) + S[RL[0]+1:]
        return S, 1
    fir = min(LR[0], RL[0])
    sec = max(LR[0], RL[0])
    S = S[:fir+1] + reverse(S[sec:fir:-1]) + S[sec+1:]
    return S, 2

def cal(S):
    ans = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            ans +=1
    return ans


ans = cal(S)
for i in range(K):
    S, res = solve(S)
    ans += res
print(ans)


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

N, K = MAP()
S = input()

def searchRL(S):
    ans = []
    for i in range(N-1):
        if S[i] == "R" and S[i+1] == "L":
            ans.append(i)
    return ans

def searchLR(S):
    ans = []
    for i in range(N-1):
        if S[i] == "L" and S[i+1] == "R":
            ans.append(i)
    return ans

def reverse(S):
    S = list(S)
    for i in range(len(S)):
        if S[i] == 'L':
            S[i] = 'R'
        if S[i] == 'R':
            S[i] = 'L'
    return ''.join(S)


def solve(S):
    if len(RL) == 0 and len(LR) == 0:
        return S, 0
    if len(RL) == 0:
        S = reverse(S[LR[0]::-1]) + S[LR[0]+1:]
        LR.pop(0)
        return S, 1
    if len(LR) == 0:
        S = reverse(S[RL[0]::-1]) + S[RL[0]+1:]
        RL.pop(0)
        return S, 1
    fir = min(LR[0], RL[0])
    sec = max(LR[0], RL[0])
    S = S[:fir+1] + reverse(S[sec:fir:-1]) + S[sec+1:]
    LR.pop(0)
    RL.pop(0)
    return S, 2

def cal(S):
    ans = 0
    for i in range(len(S)-1):
        if S[i] == S[i+1]:
            ans +=1
    return ans

RL = searchRL(S)
LR = searchLR(S)
ans = cal(S)
for i in range(K):
    S, res = solve(S)
    ans += res
print(ans)
### BUGGY CODE ###

n=int(input())
s=[input() for _ in range(n)]
ans=0
dic={}
for i in range(n):
    lst=sorted(list(s[i]))
    a=''
    for k in lst:
        a+=k
    if not a in dic.keys():
      dic[a]=1
    else: dic[a]+=1
for i in dic.values():
  ans+=i*(i-1)//2


print(ans)

### FIXED CODE ###

n=int(input())
ans=0
dic={}
for _ in range(n):
    s=input()
    s=sorted(s)
    s=''.join(s)
    if not s in dic.keys():
      dic[s]=1
    else: dic[s]+=1
for i in dic.values():
  ans+=i*(i-1)//2


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

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = ternary(data[i], 2, max_length)
        data[i] = now_bin
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    pow_data = defaultdict(int)

    ans = 0
    for i in range(num):
        now_bin = data[i]
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] -= 1
                aaa = (num - i - 1 - bit_count[j])
            else:
                aaa = bit_count[j]

            pow_num = max_length - 1 - j
            if pow_num in pow_data:
                bbb = pow_data[pow_num]
            else:
                bbb = pow(2, pow_num, mod)
                pow_data[pow_num] = bbb

            ans += bbb * aaa
            ans %= mod

    print(ans)




if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction

# 10進数表記でnのk進数を求めてlength分0埋め
def ternary (n, k, length):
    if n == 0:
        nums = ['0' for i in range(length)]
        nums = ''.join(nums)
        return nums
    nums = ''
    while n:
        n, r = divmod(n, k)
        nums += str(r)
    nums = nums[::-1]
    nums = nums.zfill(length)
    return nums


def main():
    num = int(input())
    data = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    max_length = len(bin(max(data))) - 2
    bit_count = [0 for i in range(max_length)]

    for i in range(num):
        now_bin = bin(data[i])[2:]
        now_bin = now_bin.zfill(max_length)
        for j in range(max_length):
            if now_bin[j] == "1":
                bit_count[j] += 1

    flg_data = [0 for i in range(max_length)]


    for i in range(max_length):
        flg_data[i] += bit_count[i] * (num - bit_count[i])

    ans = 0
    for j in range(max_length):
        pow_num = max_length - 1 - j
        bbb = pow(2, pow_num, mod)

        ans += bbb * flg_data[j]
        ans %= mod

    print(ans)




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

N = int(input())
counter = 0
for i in range(357, N + 1):
    string = str(i)
    count3 = string.count("3")
    count5 = string.count("5")
    count7 = string.count("7")
    #print(i, count3, count5, count7)
    if count3 + count5 + count7 == len(string) and 0 not in [count3, count5, count7]:
        counter += 1

print(counter)



### FIXED CODE ###

N = int(input())
digit = len(str(N))
list753 = ["3", "5", "7"]  # string

for i in range(digit):
    for n in list753:
        if len(n) == i:
            list753.append(n + "7")
            list753.append(n + "5")
            list753.append(n + "3")

# print(list753)
counter = 0
for num in list753:
    if int(num) <= N and 0 not in [num.count("3"), num.count("5"), num.count("7")]:
        counter += 1
print(counter)
### BUGGY CODE ###

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

sum_A = 1
for i in range(0,len(A)):
  if(A[i] == 0):
        print(0)
        exit()
  sum_A *= A[i]
if(sum_A > 1000000000000000000):
        print("-1")
        exit()
print(sum_A)


### FIXED CODE ###

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

sum_A = 1

for i in range(0,len(A)):
  if(A[i] == 0):
        print(0)
        exit()

for i in range(0,len(A)):
  if(sum_A > 1000000000000000000):
        break
  sum_A *= A[i]
if(sum_A > 1000000000000000000):
        print("-1")
        exit()
print(sum_A)
### BUGGY CODE ###

N, K = map(int, input().split())
H = sorted(list(map(int, input().split())), reverse=True)

cnt = 0
atk = 0
while True:
    for i in range(N):
        if H[i] <= 0:
            continue
        else:
            if K > 0:
                K -= 1
                H[i] = 0
                cnt += 1
            else:
                H[i] -= 1
                atk += 1
                if H[i] == 0:
                    cnt += 1

    if cnt == N:
        break

print(atk)

### FIXED CODE ###

N, K = map(int, input().split())
H = sorted(list(map(int, input().split())), reverse=True)

cnt = 0
atk = 0
while True:
    for i in range(N):
        if H[i] <= 0:
            continue
        else:
            if K > 0:
                K -= 1
                H[i] = 0
                cnt += 1
            else:
                atk += H[i]
                cnt += 1

    if cnt == N:
        break

print(atk)
### BUGGY CODE ###

class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = sum([self.data[i], self.data[i-1]])
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = sum([self.data[2*idx+1], self.data[2*idx+2]])
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 + 1 < idx2:
                if idx1&1 == 0: # idx1が偶数
                    result = sum([result, self.data[idx1]])
                if idx2&1 == 1: # idx2が奇数
                    result = sum([result, self.data[idx2]])
                    idx2 -= 1
                
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            
            if idx1 == idx2:
                result = sum([result, self.data[idx1]])
            else: # idx1 + 1 == idx2
                result = sum([result, self.data[idx1], self.data[idx2]])
            
            return result

def find_next(st, idx):
    n = len(st)
    idx_v = st.query(idx, idx)
    right_sum = st.query(idx, n) - idx_v
    if right_sum:
        left = idx
        right = n
        while left + 1 < right:
            mid = (left + right) // 2
            right_sum = st.query(idx, mid) - idx_v
            if right_sum >= 1:
                right = mid
            else:
                left = mid
        return left
    else:
        return n

def find_before(st, idx):
    if idx == 0:
        return -1
    left_sum = st.query(0, idx)
    if left_sum:
        left = 0
        right = idx
        while left + 1 < right:
            mid = (left + right) // 2
            left_sum = st.query(mid, idx)
            if left_sum:
                left = mid
            else:
                right = mid
        return left
    else:
        return -1


N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1], reverse=True)

a = [0]*N
st = SegmentTree(a)
ans = 0
for i, p in P:
  ir1 = find_next(st, i)
  ir2 = N if ir1==N else find_next(st, ir1)
  il1 = find_before(st, i)
  il2 = -1 if il1==-1 else find_before(st, il1)
  ans += ((ir1-i)*(il1-il2) + (ir2-ir1)*(i-il1)) * p
  st.update(i, 1)


print(ans)

### FIXED CODE ###

N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


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

N=int(input())

ball=list(map(int,input().split()))

num=[0]*(N+1) #それぞれの数の個数

cnb=[-1]*(N+1) #それぞれの球を抜いた時のコンビネーション

for i in range(len(ball)):
  num[ball[i]]+=1

for i in range(len(num)):
  if num[i]>=1:
    break
  if i==len(num)+1:
    for j in range(ball):
      print("0")

for j in ball:
  
  if cnb[j]==-1:
    cnb[j]=0
    num[j]-=1

    for k in range(1,len(num)):
      n=num[k]
      if n>=2:
        cnb[j]+=int(n*(n-1)/2)

    print(cnb[j])
    num[j]+=1
  else:
    print(cnb[j])

### FIXED CODE ###

N=int(input())

ball=list(map(int,input().split()))

num=[0]*(N+1) #それぞれの数の個数

cnb=[-1]*(N+1) #それぞれの球を抜いた時のコンビネーション

for i in range(len(ball)):
  num[ball[i]]+=1


allcnb=0
for i in num:
  if i>=2:
    allcnb+=int(i*(i-1)/2)

for i in ball:
  cnb=0

  if num[i]>=2:
    cnb=num[i]-1

  print(allcnb-cnb)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
    if i % 2 == 0:
        b.append(a[i])
    else:
        b.insert(0, a[i])
if n % 2 == 1:
    b.reverse()

for i in range(n):
    print(b[i], end = " ")
print()

### FIXED CODE ###

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

def print_data(a, flag):
    for i in range(n - 1, -1, -2):
        print(a[i], end = " ")
    
    for i in range(0 + flag, n, 2):
        print(a[i], end = " ")
    
    print()


if n % 2 == 0:
    print_data(a, 0)
else:
    print_data(a, 1)