Problem:


Score: 500 points

Problem Statement

Given is a permutation P of \{1, 2, \ldots, N\}.

For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.

Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Constraints

 2 \le N \le 10^5 

 1 \le P_i \le N 

 P_i \neq P_j  (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Sample Input 1

3
2 3 1

Sample Output 1

5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

30

Sample Input 3

8
8 2 7 3 4 5 6 1

Sample Output 3

136



Sample input:
3
2 3 1


Sample output:
5

Submission status: Accepted

Solution code:
class Avltree:

  def __init__(self, key=None):
    self.key=key
    self.left=None
    self.right=None
    self.balance="Even"

  def search(self,key):
    node=self
    while node is not None:
      if node.key==key:
        return node
      if node.key>key:
        node=node.left
      elif node.key < key:
        node=node.right
    return None

  def search_lower(self, key, key_lower):
    node=self
    if node.key is None:
      return key_lower
    ans=key_lower
    while node is not None:
      if node.key<key:
        if ans<node.key:
          ans=node.key
        node=node.right
      elif node.key>=key:
        node=node.left
    return ans

  def search_higher(self, key, key_higher):
    node=self
    if node.key is None:
      return key_higher
    ans=key_higher
    while node is not None:
      if node.key>key:
        if ans>node.key:
          ans=node.key
        node=node.left
      elif node.key<=key:
        node=node.right
    return ans

  def end_lower(self, end_lower_key):
    node=self
    while node.left is not None:
      node=node.left
    return node.key

  def end_higher(self, end_higher_key):
    node=self
    while node.right is not None:
      node=node.right
    return node.key

  def DoubleRightRotation(self):
    tl=self.left
    self.left=tl.right.right
    tl.right.right=self
    tlr=tl.right
    tl.right=tlr.left
    tlr.left=tl
    if tlr.balance=="Left":
      tlr.right.balance="Right"
      tlr.left.balance="Even"
    elif tlr.balance=="Right":
      tlr.right.balance="Even"
      tlr.left.balance="Left"
    elif tlr.balance=="Even":
      tlr.right.balance="Even"
      tlr.left.balance="Even"
    tlr.balance="Even"
    return tlr

  def DoubleLeftRotation(self):
    tr=self.right
    self.right=tr.left.left
    tr.left.left=self
    trl=tr.left
    tr.left=trl.right
    trl.right=tr
    if trl.balance=="Right":
      trl.left.balance="Left"
      trl.right.balance="Even"
    elif trl.balance=="Left":
      trl.left.balance="Even"
      trl.right.balance="Right"
    elif trl.balance=="Even":
      trl.left.balance="Even"
      trl.right.balance="Even"
    trl.balance="Even"
    return trl

  def SingleLeftRotation(self):
    tr=self.right
    tr.balance="Even"
    self.balance="Even"
    self.right=tr.left
    tr.left=self
    return tr

  def SingleRightRotation(self):
    tl=self.left
    tl.balance="Even"
    self.balance="Even"
    self.left=tl.right
    tl.right=self
    return tl

  def replace(self, p, v):
    if p.left==self:
      p.left=v
    else:
      p.right=v

  def insert(self, key):
    if self.key is None:
      self.key=key
      return self
    if key<self.key:
      if self.left is None:
        self.left=Avltree(key)
      else:
        self.left.insertx(self, key)
    elif key>self.key:
      if self.right is None:
        self.right=Avltree(key)
      else:
        self.right.insertx(self, key)
    else:
      pass

  def insertx(self, p, key):
    node=self
    s=[]
    while True:
      if node.key>key:
        s.append((node, -1))
        if node.left is None:
          node.left=Avltree(key)
          node=node.left
          break
        else:
          node=node.left
      elif node.key<key:
        s.append((node, 1))
        if node.right is None:
          node.right=Avltree(key)
          node=node.right
          break
        else:
          node=node.right
    while len(s)!=0:
      node,direct=s.pop()
      if len(s)!=0:
        par=s[-1][0]
      else:
        par=p
      if direct==-1:
        if node.balance=="Right":
          node.balance="Even"
          break
        elif node.balance=="Even":
          node.balance="Left"
        elif node.balance=="Left":
          if node.left.balance=="Right":
            node.replace(par,node.DoubleRightRotation())
          elif node.left.balance=="Left":
            node.replace(par,node.SingleRightRotation())
          break
      elif direct==1:
        if node.balance=="Left":
          node.balance="Even"
          break
        elif node.balance=="Even":
          node.balance="Right"
        elif node.balance=="Right":
          if node.right.balance=="Left":
            node.replace(par,node.DoubleLeftRotation())
          elif node.right.balance=="Right":
            node.replace(par,node.SingleLeftRotation())
          break

  def to_s(self):
    return self.key

  def left_s(self):
    if self.left is None:
      return None
    return (self.left).key

  def right_s(self):
    if self.right is None:
      return None
    return (self.right).key

n=int(input())
p=list(map(int,input().split()))
ans=0
l=[0]*n
for i in range(n):
  l[p[i]-1]=i
root=Avltree()
for i in range(n-1,-1,-1):
  root.insert(l[i])
  ans+=(i+1)*(root.search_lower(l[i],-1)-root.search_lower((root.search_lower(l[i],-1)),-1))*(root.search_higher(l[i],n)-l[i])
  ans+=(i+1)*(l[i]-root.search_lower(l[i],-1))*(root.search_higher(root.search_higher(l[i],n),n)-root.search_higher(l[i],n))
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = [int(x) for x in input().split()]

PIdx = sorted([(i + 1, v) for i, v in enumerate(P)], key = lambda x: x[1])

L = [0]
for i in range(N + 1):
    L.append(i)

R = [i + 1 for i in range(N + 1)]
R.append(N + 1)

ans = 0
for i, v in PIdx:
    l1 = L[i]
    l2 = L[l1]
    r1 = R[i]
    r2 = R[r1]

    ans += v * ((i - l1) * (r2 - r1) + (l1 - l2) * (r1 - i))

    L[r1] = l1
    R[l1] = r1

print(ans)

Submission status: Accepted

Solution code:
class BIT:
  def __init__(self, n):
    self.N = n
    self.tree = [0]*(n+1)
  
  def BIT_add(self, i):
    while i <= self.N:
      self.tree[i] += 1
      i += i&(-i)
  
  def BIT_sum(self, i):
    s = 0
    while i:
      s += self.tree[i]
      i -= i&(-i)
    return s
  
  def BIT_search(self, x):
    i = 0
    s = 0
    step = 1<<(self.N.bit_length()-1)
    
    while step:
      if i+step <= self.N and s+self.tree[i+step] < x:
        i += step
        s += self.tree[i]
      step >>= 1
    return i+1

N = int(input())
bit = BIT(N)
p = [None]+[int(c) for c in input().split()]
p_to_i = [None]*(N+1)
for i, x in enumerate(p[1:], 1):
  p_to_i[x] = i
  
ans = 0
for x in range(N,0,-1):
  c = p_to_i[x]
  L = bit.BIT_sum(c)
  bit.BIT_add(c)
  R = N-x-L
  a = bit.BIT_search(L-1) if L>=2 else 0
  b = bit.BIT_search(L) if L >= 1 else 0
  d = bit.BIT_search(L+2) if R >= 1 else N+1
  e = bit.BIT_search(L+3) if R >= 1 else N+1
  
  coef = 0
  if b != 0:
    coef += (b-a) * (d-c)
  if d != 0:
    coef += (e-d) * (c-b)
  
  ans += x*coef
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def bisearch_left(self, l, r, x):
        """ 区間[l,r]で左からx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return -1

    def bisearch_right(self, l, r, x):
        """ 区間[l,r]で右からx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -1

N = INT()
A = LIST()
# aの昇順に処理できるようにindexで並べておく
idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i

bit = BIT(N)
ans = [0] * (N+1)
# 大きいaから見ていく
for a in range(N, 0, -1):
    # a(N~1)が格納されているindex
    idx = idxs[a]
    # 自分より小さいindexで2回目に自分より大きい値がある直前の場所
    res = bit.bisearch_right(0, idx, 2)
    p = res + 1 if res != -1 else 0
    # 自分より小さいindexで最初に自分より大きい値がある直前の場所
    res = bit.bisearch_right(0, idx, 1)
    q = res + 1 if res != -1 else 0
    # 自分より大きいindexで最初に自分より大きい値がある直前の場所
    res = bit.bisearch_left(idx, N-1, 1)
    r = res - 1 if res != -1 else N - 1
    # 自分より大きいindexで2回目に自分より大きい値がある直前の場所
    res = bit.bisearch_left(idx, N-1, 2)
    s = res - 1 if res != -1 else N - 1
    # aを使う回数 * a = (左に自分より大きい値がある時の通り数 + 右に自分より大きい値がある時の通り数) * a
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    # aを出現済とする
    bit.add(idx, 1)
# 全てのaについての合計
print(sum(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def bisearch_left(self, l, r, x):
        """ 区間[l,r]で左からx番目の値がある位置 """
        l_sm = self.sum(l-1)
        ok = r + 1
        ng = l - 1
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return -1

    def bisearch_right(self, l, r, x):
        """ 区間[l,r]で右からx番目の値がある位置 """
        r_sm = self.sum(r)
        ok = l - 1
        ng = r + 1
        while ok+1 < ng:
            mid = (ok+ng) // 2
            if r_sm - self.sum(mid-1) >= x:
                ok = mid
            else:
                ng = mid
        if ok != l - 1:
            return ok
        else:
            return -1

N = INT()
A = LIST()
# aの昇順に処理できるようにindexで並べておく
idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i + 1

bit = BIT(N+2)
# 先頭と末尾に番兵を仕込む
bit.add(0, 2)
bit.add(N+1, 2)
ans = [0] * (N+1)
# 大きいaから見ていく
for a in range(N, 0, -1):
    # a(N~1)が格納されているindex
    idx = idxs[a]
    # 自分より小さいindexで2回目に自分より大きい値がある直前の場所
    p = bit.bisearch_right(0, idx, 2) + 1
    # 自分より小さいindexで最初に自分より大きい値がある直前の場所
    q = bit.bisearch_right(0, idx, 1) + 1
    # 自分より大きいindexで最初に自分より大きい値がある直前の場所
    r = bit.bisearch_left(idx, N+1, 1) - 1
    # 自分より大きいindexで2回目に自分より大きい値がある直前の場所
    s = bit.bisearch_left(idx, N+1, 2) - 1
    # aを使う回数 * a = (左に自分より大きい値がある時の通り数 + 右に自分より大きい値がある時の通り数) * a
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    # aを出現済とする
    bit.add(idx, 1)
# 全てのaについての合計
print(sum(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:

    def __init__(self, n):
        # 0-indexed
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def bisearch_left(self, l, r, x):
        """ 区間l,rで左からx番目の値がある位置 """
        l_val = self.sum(l)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if self.sum(mid) - l_val >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def bisearch_right(self, l, r, x):
        """ 区間l,rで右からx番目の値がある位置 """
        r_val = self.sum(r)
        ok = r
        ng = l
        while ng+1 < ok:
            mid = (ok+ng) // 2
            if r_val - self.sum(mid) < x:
                ok = mid
            else:
                ng = mid
        return ok

N = INT()
A = LIST()
# aの昇順に処理できるようにindexで並べておく
idxs = [0] * (N+1)
for i, a in enumerate(A):
    idxs[a] = i + 1

bit = BIT(N+2)
# 先頭と末尾に番兵を仕込む
bit.add(0, 2)
bit.add(N+1, 2)
ans = [0] * (N+1)
# 大きいaから見ていく
for a in range(N, 0, -1):
    # a(N~1)が格納されているindex
    idx = idxs[a]
    # 自分より小さいindexで2回目に自分より大きい値がある直前の場所
    p = bit.bisearch_right(-1, idx, 2) + 1
    # 自分より小さいindexで最初に自分より大きい値がある直前の場所
    q = bit.bisearch_right(-1, idx, 1) + 1
    # 自分より大きいindexで最初に自分より大きい値がある直前の場所
    r = bit.bisearch_left(idx, N+1, 1) - 1
    # 自分より大きいindexで2回目に自分より大きい値がある直前の場所
    s = bit.bisearch_left(idx, N+1, 2) - 1
    # aを使う回数 * a = (左に自分より大きい値がある時の通り数 + 右に自分より大きい値がある時の通り数) * a
    ans[a] = ((q-p)*(r-idx+1) + (idx-q+1)*(s-r)) * a
    # aを出現済とする
    bit.add(idx, 1)
# 全てのaについての合計
print(sum(ans))

Submission status: Accepted

Solution code:
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) > w
        if w < 0:
            return 0
        idx = 0  # self.bit[idx] <= w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


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

p2idx = [0] * (n + 1)
for i in range(1, n + 1):
    p2idx[p[i - 1]] = i

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt
    # print(x, idx, idx_l, idx_r, (idx - idx_l) * (idx_r - idx))

print(ans)

Submission status: Accepted

Solution code:
class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def build(self, data):
        pass

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s

    def bisect_left(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) >= w
        if w <= 0:
            return 0
        idx = 0  # self.bit[idx] < w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] < w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1

    def bisect_right(self, w):
        # condition : always all element is not minus
        # return minimum idx where bit.sum(idx) > w
        if w < 0:
            return 0
        idx = 0  # self.bit[idx] <= w
        k = 1 << ((self.n).bit_length() - 1)
        while k > 0:
            if idx + k <= self.n and self.bit[idx + k] <= w:
                w -= self.bit[idx + k]
                idx += k
            k = k >> 1
        return idx + 1


n = int(input())
p = [0] + list(map(int, input().split()))

p2idx = [0] * (n + 1)
for i in range(1, n + 1):
    p2idx[p[i]] = i

ans = 0
bit = BIT1(n)
for x in reversed(range(1, n + 1)):
    idx = p2idx[x]
    bit.add(idx, 1)
    idx_rank = bit.sum(idx)
    idx_l2 = bit.bisect_left(idx_rank - 2)
    idx_l1 = bit.bisect_left(idx_rank - 1)
    idx_r1 = bit.bisect_left(idx_rank + 1)
    idx_r2 = bit.bisect_left(idx_rank + 2)

    cnt = 0
    cnt += (idx_l1 - idx_l2) * (idx_r1 - idx)
    cnt += (idx - idx_l1) * (idx_r2 - idx_r1)
    ans += x * cnt
    # print(x, idx, idx_l, idx_r, (idx - idx_l) * (idx_r - idx))

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r),self.sum(l))

    def bisect_left(self,w,increase=True):
        n=self.__n
        k=2**((self.__n-1).bit_length())
        res=0
        now=self.__e
        while(k):
            if(res+k<=n and self.__dot(now,self.__node[res+k])<w and increase):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            elif(res+k<=n and self.__dot(now,self.__node[res+k])>w and (not increase)):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            k//=2
        return res

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    idx=[0]*n
    for i,a in enumerate(A):
        idx[a-1]=i

    from operator import add
    bit=BIT([0]*n,add,0)

    ans=0
    for k in range(n,0,-1):
        i=idx[k-1]
        bit.add(i)
        s=bit.sum(i+1)
        l0=bit.bisect_left(s-1)-(s<=1)
        l1=bit.bisect_left(s-2)-(s<=2)
        r0=bit.bisect_left(s+1)
        r1=bit.bisect_left(s+2)
        ans+=k*((i-l0)*(r1-r0)+(l0-l1)*(r0-i))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        i+=1
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r-1),self.sum(l-1))

    def bisect_left(self,w,increase=True):
        n=self.__n
        k=2**((self.__n-1).bit_length())
        res=0
        now=self.__e
        while(k):
            if(res+k<=n and self.__dot(now,self.__node[res+k])<w and increase):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            elif(res+k<=n and self.__dot(now,self.__node[res+k])>w and (not increase)):
                now=self.__dot(now,self.__node[res+k])
                res+=k
            k//=2
        return res

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    idx=[0]*n
    for i,a in enumerate(A):
        idx[a-1]=i

    from operator import add
    bit=BIT([0]*n,add,0)

    ans=0
    for k in range(n,0,-1):
        i=idx[k-1]
        bit.add(i)
        s=bit.sum(i)
        l0=bit.bisect_left(s-1)-(s<=1)
        l1=bit.bisect_left(s-2)-(s<=2)
        r0=bit.bisect_left(s+1)
        r1=bit.bisect_left(s+2)
        ans+=k*((i-l0)*(r1-r0)+(l0-l1)*(r0-i))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w=1):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        i+=1
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res

    def range_sum(self,l,r):
        assert(self.__inv)
        return self.__inv(self.sum(r),self.sum(l))

    def bisect_left(self,w,increase=True):
        if(w>self.sum(self.__n-1)): return self.__n
        n=2**((self.__n-1).bit_length())
        res=0
        while(n>0):
            if(res+n<=self.__n and ((w>self.__node[res+n])^(not increase))):
                w-=self.__node[res+n]
                res+=n
            n//=2
        return res

def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    idx=[0]*n
    for i,a in enumerate(A): idx[a-1]=i
    from operator import add
    bit=BIT([0]*n,add,0)

    # calculate
    ans=0
    for k in range(n,0,-1):
        i=idx[k-1]
        bit.add(i)
        s=bit.sum(i)
        l0=bit.bisect_left(s-1)-(s<=1)
        l1=bit.bisect_left(s-2)-(s<=2)
        r0=bit.bisect_left(s+1)
        r1=bit.bisect_left(s+2)
        ans+=k*((l0-l1)*(r0-i)+(r1-r0)*(i-l0))
    print(ans)
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    n = II()
    print(n**3)
    return

#B
def B():
    n = II()
    a = LI()
    b = LI()
    c = LI()
    ans = 0
    for i in range(n):
        ans += b[a[i] - 1] + (c[a[i] - 1] if i != n - 1 and a[i] + 1 == a[i + 1] else 0)
    print(ans)
    return

#C
def C():
    n = II()
    b = LI()
    ans = b[0]
    for i in range(n-2):
        if b[i] >= b[i + 1]:
            ans += b[i + 1]
        else:
            ans += b[i]
    print(ans+b[-1])
    return

#D
def D():
    n, k = LI()
    s = S()
    a = []
    for i in range(n):
        if i == n - 1:
            a.append(s[i])
        elif s[i] != s[i + 1]:
            a.append(s[i])
    print(min(n - 1, n - len(a) + 2 * k))
    return

# E
# 解説AC
# Piが何個使えるかというとこまでは良くて
# そのPiよりも大きい数字が左に2個右に2個必要というところまではいけた
# 問題の本質を解決できてはいない
# ここから解説
# 大きい順からみて見たものに対してインデックスを保持
# ここからbisectを使えばlogNでi付近のすでに追加したインデックスを持ってこれる
# あと少しだけどその少しが遠い
# ↑
# これは嘘
# BITを使え
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i
        while x < self.size:
            self.bit[x] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i
        while x > 0:
            res += self.bit[x]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        ok = self.size
        ng = 0
        while abs(ok - ng) != 1:
            mid = (ok + ng)//2
            if self.sum(mid) >= x:
                ok = mid
            else:
                ng = mid
        return ok

    def __len__(self):
        return self.size

def E():
    n = II()
    a = LI()
    dic = defaultdict(int)
    for i, ai in enumerate(a):
        dic[ai] = i+1
    bit = BinaryIndexedTree(n+1)
    num = [i + 1 for i in range(n)][::-1]
    ans = 0
    for i in num:
        c = dic[i]
        L = bit.sum(c)
        bit.add(c,1)
        R = n-i-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
        tmp = 0
        if b != 0:
            tmp += (b-a) * (d-c)
        if d != 0:
            tmp += (e-d) * (c-b)
        ans += i * tmp

    print(ans)
    return

#F
def F():
    return


#Solve
if __name__ == '__main__':
    E()