CodeEff/ECCO huggingface dataset:
# Original solution
from operator import itemgetter


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    if d == 1:
        print(n)
        continue
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)

# Optimized solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    if d == 1:
        print(n)
        continue
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)
# Original solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)

# Optimized solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
res = [0] * m
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    res[d - 1] = cnt

print('\n'.join(map(str, res)), end='\n')
# Original solution
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
res = [0] * m
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    res[d - 1] = cnt

print('\n'.join(map(str, res)), end='\n')


# Optimized solution
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


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

for i in range(n):
    info[i] = info[i][0], info[i][1], info[i][1] - info[i][0] + 1
info = sorted(info, key=itemgetter(2))

bit = BIT(m + 1)
l_info = 0
ans = n
res = [0] * m
for d in range(1, m + 1):
    while True:
        if l_info < n and info[l_info][2] < d:
            l, r, _ = info[l_info]
            bit.add(l, r + 1, 1)
            l_info += 1
            ans -= 1
        else:
            break
    cnt = ans
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    res[d - 1] = cnt

print('\n'.join(map(str, res)), end='\n')
# Original solution
import sys
input=sys.stdin.readline

#区間[L,R]に1を加えていく
def seg_tree_update(L,R):
    L,R=2**m-1+L,2**m-1+R
    while L<R:
        if L%2==0:
            tree[L]+=1
        if R%2==1:
            tree[R]+=1
        L//=2
        R=R//2-1
    if L==R:
        tree[L]+=1

#数直線xでの和を求める
def seg_tree_sumarize(x):
    ind=2**m-1+x
    SUM=0
    while ind>=0:
        SUM+=tree[ind]
        ind=(ind-1)//2
    return SUM

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

data=[]

for i in range(N):
    l,r=list(map(int,input().split()))
    data.append([r-l, l, r])

data.sort()

m=0
while pow(2,m)<M+1:
    m+=1
tree=[0]*(pow(2,m+1)-1)

i=0
for d in range(1,M+1):
    
    #間隔の長さがd以下の区間だけ考えれば良い。
    while i<N and data[i][0]<d:
        seg_tree_update(data[i][1],data[i][2])
        i+=1
    
    ans=0
    
    for j in range((M+1)//d+1):
        if d*j>M:
            break
        ans+=seg_tree_sumarize(d*j)
    
    print((ans+N-i))

# Optimized solution
"""
BIT
区間[L,R]にxを加える。
座標Xでの値を求める。
"""
import sys
input=sys.stdin.readline

def bit_add(i,x):
    while i<=M:
        tree[i]+=x
        i+=i&(-i)

def bit_sum(i):
    s=0
    while i>0:
        s+=tree[i]
        i-=i&(-i)
    return s

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

data=[]
for i in range(N):
    l,r=list(map(int,input().split()))
    data.append([r-l, l, r])
data.sort()

k=0
tree=[0]*(M+1)
for d in range(1,M+1):
    
    #間隔の長さがd以下の区間だけ考えれば良い。
    while k<N and data[k][0]<d:
        bit_add(data[k][1],1)
        bit_add(data[k][2]+1,-1)
        k+=1
    
    ans=0
    for j in range(1,M//d+1):
        ans+=bit_sum(d*j)
    
    print((ans+N-k))
# Original solution

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


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

bitA = [0] * (M+2)
bitB = [0] * (M+2)

len_LR = []

for i in range(N):

    l,r = list(map(int,input().split()))
    len_LR.append([r-l,l,r])

len_LR.sort()
len_LR.append([float("inf"),0,float("inf")])
ind = 0
ns = N
ans = []

for d in range(M):

    d += 1

    while len_LR[ind][2]-len_LR[ind][1]+1 < d:

        bitaddR(len_LR[ind][1] , len_LR[ind][2]+1 , 1 ,bitA,bitB)
        ns -= 1
        ind += 1

    np = 0

    for i in range(d,M+1,d):
        np += bitsumR(i+1,bitA,bitB) - bitsumR(i,bitA,bitB)

    ans.append(ns + np)

print(("\n".join(map(str,ans))))


# Optimized solution

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(x,bit): #ind 1～aまでの和を求める
   
    ret = 0
    while x:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret


#区間更新BIT(BITを2つ用意し、BITの長さをN+2で初期化しておくべし)
def bitaddR(l,r,w,bit1,bit2): #半開区間[l,r)にwを加える

    bitadd(l,-1*w*l,bit1)
    bitadd(r,w*r,bit1)
    bitadd(l,w,bit2)
    bitadd(r,-1*w,bit2)

def bitsumR(r,bit1,bit2): #半開区間[1,r)の区間和

    return bitsum(r,bit1) + r * bitsum(r,bit2)


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

BIT = [0] * (M+1)
dic = {}
for i in range(N):
    l,r = list(map(int,input().split()))
    if r-l+1 not in dic:
        dic[r-l+1] = []
    dic[r-l+1].append([l,r])

ind = 0
ns = N
ans = []
for d in range(M):

    d += 1

    if d in dic:
        for L,R in dic[d]:

            bitadd(L , 1 ,BIT)
            bitadd(R+1 , -1 , BIT)
            ns -= 1

    nm = 0
    for i in range(d,M+1,d):
        
        nm += bitsum(i,BIT)
    ans.append(nm+ns)

print(("\n".join(map(str,ans))))
# Original solution
a,b,c,d,e,f=[int(eval(input())) for _ in range(6)]
print((sum([a,b,c,d,max(e,f)])-min([a,b,c,d])))

# Optimized solution
print((sum(sorted(int(eval(input())) for _ in range(4))[1:])+max([int(eval(input())) for _ in range(2)])))
# Original solution
N = int(eval(input()))
print(((N - 1) // 2))

# Optimized solution

N = int(eval(input()))
print((N // 2 - int(N % 2 == 0)))
# Original solution
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs= sys.stdin.buffer.readlines
#rstrip().decode('utf-8')

import math
#import numpy as np
#import operator
#import bisect
#from heapq import heapify,heappop,heappush
#from math import gcd
#from fractions import gcd
#from collections import deque
#from collections import defaultdict
#from collections import Counter
#from itertools import accumulate
#from itertools import groupby
#from itertools import permutations
#from itertools import combinations
#from scipy.sparse import csr_matrix
#from scipy.sparse.csgraph import floyd_warshall
#from scipy.sparse.csgraph import csgraph_from_dense
#from scipy.sparse.csgraph import dijkstra
#sys.setrecursionlimit(10**7)

#map(int,input().split())

def main():
	
	n=int(eval(input()))
	print(((n-1)//2))



	

if __name__ == '__main__':
	main()

# Optimized solution
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(eval(input()))
def MI(): return list(map(int,input().split()))
def MF(): return list(map(float,input().split()))
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n=II()

	print(((n-1)//2))









if __name__ == "__main__":
	main()
# Original solution
N=int(eval(input()))
S=set()
for i in range(1,N):
    x=i
    y=N-i
    if x<y:
        S.add(x)
print((len(S)))


# Optimized solution
print(((int(eval(input()))-1)//2))
# Original solution
a=int(eval(input()))
if a%2==0:
    print((a//2-1))
else:
    print((a//2))

# Optimized solution
print(((int(eval(input()))-1)//2))
# Original solution
print(((int(eval(input()))-1)//2))

# Optimized solution
N = int(eval(input()))
if N%2==0:
    print((N//2-1))
else:
    print((N//2))
# Original solution
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
if n%2:
    print((n//2))
else:
    print((n//2-1))

# Optimized solution
n = int(eval(input()))
print(((n-1)//2))
# Original solution
N = int(eval(input()))
if N % 2 == 0:
  print((N//2-1))
else:
  print((N//2))

# Optimized solution
# coding: utf-8

N=  int(eval(input()))

if N%2 == 0:
    print((N//2-1))
else:
    print((N//2))
# Original solution
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    cnt = 0
    for i in range(1, n // 2 + 1):
        if n - i != i:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()


# Optimized solution
import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    cnt = 0
    for i in range(1, n // 2 if n % 2 == 0 else n // 2 + 1):
        if n - i <= n:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()
# Original solution
n=int(eval(input()))-1
print((n//2))

# Optimized solution
print(((int(eval(input()))-1)//2))
# Original solution
def main():
    while True:
        N = eval(input())    
        if N == 0:
            break
        points = [Vector(list(map(int, input().split()))) for _ in range(N)]
        seq = [Vector([0, -1]), Vector([0, 0])]
        while len(points) != 0:
            pre = seq[-1] - seq[-2]
            points.sort(key=lambda x: abs(x-seq[-1]), reverse=True)
            points.sort(key=lambda x: (x-seq[-1]).norm() * pre.norm())
            p = [(x-seq[-1]).norm() * pre.norm() for x in points]
            seq += [points.pop()]
        print(round(sum(abs(v2 - v1) for v1, v2 in zip(seq[1:], seq[2:])), 1))

class Vector(tuple):

    def __neg__(self):
        return Vector([-x for x in self])

    def __abs__(self):
        return sum(x ** 2 for x in self) ** 0.5

    def __add__(self, v):
        if len(self) != len(v):
            raise ValueError("Same dimension is required.")
        return Vector([x1 + x2 for x1, x2 in zip(self, v)])

    def __sub__(self, v):
        return self.__add__(-v)
    
    def norm(self):
        a = self.__abs__()
        return Vector([x / a for x in self])

    def __mul__(self,  v):
        """dot product"""
        if len(self) != len(v):
            raise ValueError("Same dimension is required.")
        #  sum(x1 * x2 for x1, x2 in zip(self, v))
        return round(sum(x1 * x2 for x1, x2 in zip(self, v)), 14)

if __name__ == "__main__":
    main()

# Optimized solution
def main():
    while True:
        N = eval(input())    
        if N == 0:
            break
        points = [Vector(list(map(int, input().split()))) for _ in range(N)]
        seq = [Vector([0, -1]), Vector([0, 0])]
        while len(points) != 0:
            pre = seq[-1] - seq[-2]
            points.sort(key=lambda x: abs(x-seq[-1]), reverse=True)
            points.sort(key=lambda x: (x-seq[-1]).norm() * pre.norm())
            seq += [points.pop()]
        print(round(sum(abs(v2 - v1) for v1, v2 in zip(seq[1:], seq[2:])), 1))

class Vector(tuple):

    def __neg__(self):
        return Vector([-x for x in self])

    def __abs__(self):
        return sum(x ** 2 for x in self) ** 0.5

    def __add__(self, v):
        if len(self) != len(v):
            raise ValueError("Same dimension is required.")
        return Vector([x1 + x2 for x1, x2 in zip(self, v)])

    def __sub__(self, v):
        return self.__add__(-v)
    
    def norm(self):
        a = self.__abs__()
        return Vector([x / a for x in self])

    def __mul__(self,  v):
        """dot product"""
        if len(self) != len(v):
            raise ValueError("Same dimension is required.")
        return round(sum(x1 * x2 for x1, x2 in zip(self, v)), 14)

if __name__ == "__main__":
    main()
# Original solution
from bisect import insort, bisect
N = int(eval(input()))
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    b = bisect(memo, i)
    l1 = memo[b-1] if b > 0 else -1
    l2 = memo[b-2] if b > 1 else -1
    r1 = memo[b+0] if b < N-p else N
    r2 = memo[b+1] if b < N-p-1 else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    insort(memo, i)

print(ans)


# Optimized solution
N = int(eval(input()))
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

print(ans)
# Original solution
# maspyさんのコード参照
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    # i = 0
    # s = 0
    # step = 1<<(N.bit_length()-1)
    # while step:
    #     if i+step <= N and s + tree[i+step] < x:
    #         i += step
    #         s += tree[i]
    #     step >>= 1
    # return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)





# Optimized solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N = int(eval(input()))
P = [None] + [int(x) for x in input().split()]
p_to_i = [None] * (N+1)
for i,x in enumerate(P[1:],1):
    p_to_i[x] = i

# 大きい数から挿入していく
# 左隣にあるインデックスを取得できるようにしておく
# そのために、[1,i]内で書き込んだ数の個数を獲得できるBITを持つ

# BITは一番最後の1ビットの位置が重要なので0ではなく1始まり。そのためNまでループする
def BIT_add(i):
    while i <= N:
        tree[i] += 1
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
    # i = 0
    # s = 0
    # step = 1<<(N.bit_length()-1)
    # while step:
    #     if i+step <= N and s + tree[i+step] < x:
    #         i += step
    #         s += tree[i]
    #     step >>= 1
    # return i+1
    left = 0
    right = N
    while right - left > 1:
        mid = (left + right) // 2
        if BIT_sum(mid) >= x:
            right = mid
        else:
            left = mid
    return right

tree = [0] * (N+1)
answer = 0
for x in range(N,0,-1):
    c = p_to_i[x]
    L = BIT_sum(c) # 左にある既に書き込んだ数の個数
    BIT_add(c)
    R = N-x-L # 右にある既に書き込んだ数の個数
    a = BIT_search(L-1) if L >= 2 else 0
    b = BIT_search(L) if L >= 1 else 0
    d = BIT_search(L+2) if R >= 1 else N+1
    e = BIT_search(L+3) if R >= 2 else N+1
    coef = 0
    if b != 0:
        # [b,c]を含むようにする。(a,b) と(c,d)が自由
        coef += (b-a) * (d-c)
    if d != 0:
        # [c,d]を含むようにする。
        coef += (e-d) * (c-b)
    answer += x * coef
print(answer)
# Original solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,q[0][0],n,n]
    ans = 0
    cnt = 3
    for i, p in q[1:]:
        l_i = bisect(le,i,2,cnt)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
        cnt += 1
    return ans

n = int(readline())
ppp = list(map(int,readline().split()))
print((solve(n, ppp)))

# Optimized solution
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

n = int(readline())
ppp = list(map(int,readline().split()))

def BIT_add(i,x):
    while i <= n:
        tree[i] += x
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
      i = 0
      s = 0
      step = 1<<(n.bit_length()-1)
      while step:
          if i+step <= n and s + tree[i+step] < x:
              i += step
              s += tree[i]
          step >>= 1
      return i+1

q = sorted(enumerate(ppp,1),key=itemgetter(1),reverse=True)
tree = [0]*(n+1)

ans = 0
for i, p in q:
    L = BIT_sum(i) # 左にある既に書き込んだ数の個数
    BIT_add(i,1)
    R = n-p-L # 右にある既に書き込んだ数の個数
    LL = BIT_search(L-1) if L >= 2 else 0
    LR = BIT_search(L) if L >= 1 else 0
    RL = BIT_search(L+2) if R >= 1 else n+1
    RR = BIT_search(L+3) if R >= 2 else n+1
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
print(ans)