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 Node:
    def __init__(self, key=None):
        self.key = key
        self.balance = 'E'
        self.parent = None
        self.left = None
        self.right = None


class AVL:
    def __init__(self):
        self.root = Node()
        self.root.parent = Node('nil')

    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
            
        return self.rebalance(p, new_node, key)
            
    def rebalance(self, u, v, key):
        while u.key != 'nil':
            if u.key > v.key:
                if u.balance == 'R':
                    u.balance = 'E'
                    return
                elif u.balance == 'L':
                    if v.balance == 'L':
                        self.rotate_R(u, v)
                        return
                    elif v.balance == 'R':

                        self.rotate_LR(u, v)
                        return
                else:
                    u.balance = 'L'
                    v = u
                    u = u.parent
            else:
                if u.balance == 'L':
                    u.balance = 'E'
                    return
                elif u.balance == 'R':
                    if v.balance == 'R':
                        self.rotate_L(u, v)
                        return
                    elif v.balance == 'L':
                        self.rotate_RL(u, v)
                        return
                else:
                    u.balance = 'R'
                    v = u
                    u = u.parent
              
    def replace(self, u, v):
        if u.parent.left == u:
            u.parent.left = v
        else:
            u.parent.right = v
        v.parent = u.parent
        if v.parent.key == 'nil':
            self.root = v   

    def rotate_R(self, u, v):
        w = v.right

        self.replace(u, v)
        v.right = u
        u.parent = v        
        u.left = w        
        if w:
            w.parent = u
        u.balance = 'E'
        v.balance = 'E'           

    def rotate_L(self, u, v):
        w = v.left
        
        self.replace(u, v)
        v.left = u
        u.parent = v
        u.right = w        
        if w:
            w.parent = u
        u.balance = 'E'
        v.balance = 'E' 

    def rotate_LR(self, u, v):
        w = v.right
        
        self.replace(u, w)
        if w.left:
            v.right = w.left
            v.right.parent = v
        else:
            v.right = None
        if w.right:
            u.left = w.right
            u.left.parent = u
        else:
            u.left = None
        v.parent = w
        w.left = v
        u.parent = w
        w.right = u

        if w.balance == 'R':
            u.balance = 'E'
            v.balance = 'L'
        elif w.balance == 'L':
            u.balance ='R'
            v.balance = 'E'
        else:
            u.balance = 'E'
            v.balance = 'E'
        w.balance = 'E'        

    def rotate_RL(self, u, v):
        w = v.left
        
        self.replace(u, w)
        if w.left:
            w.left.parent = u
            u.right = w.left
        else:
            u.right = None
        if w.right:
            w.right.parent = v
            v.left = w.right
        else:
            v.left = None
        u.parent = w
        w.left = u
        v.parent = w
        w.right = v       
        
        if w.balance == 'R':
            u.balance = 'L'
            v.balance = 'E'
        elif w.balance == 'L':
            u.balance ='E'
            v.balance = 'R'
        else:
            u.balance = 'E'
            v.balance = 'E'
        w.balance = 'E'

    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return 
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent.key != 'nil' and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent.key != 'nil':
                return cursor.parent
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():
#    import random
    import sys

#    N = 100000
#    P = list(range(1, N + 1))
#    random.shuffle(P)
    
    input = sys.stdin.readline
    N = int(input())
    P = map(int, input().split())    
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,  key=None):

        self.key = key
        self.height = 1
        self.parent = None
        self.left = None
        self.right = None


def update_height(t):
    if t.left is not None:
        l = t.left.height
    else:
        l = 0
    if t.right is not None:
        r = t.right.height
    else:
        r = 0
    
    if l >= r:
        t.height = l + 1
    else:
        t.height = r + 1


class AVL:
    def __init__(self):
        self.root = Node()       
    
    def insert(self, key):
        #値の挿入
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node

        #バランスの確認
        cursor = p
        while cursor:
            if cursor.left is not None:
                l = cursor.left.height
            else:
                l = 0
            if cursor.right is not None:
                r = cursor.right.height
            else:
                r = 0
            balance = l - r
            
            if balance == 0:
                break
            elif balance == 2:
                if key < cursor.left.key:
                    self.rotate_r(cursor)
                else:
                    self.rotate_lr(cursor)
                break
            elif balance == -2:
                if key > cursor.right.key:
                    self.rotate_l(cursor)
                else:
                    self.rotate_rl(cursor)
                break
            else:
                update_height(cursor)
                cursor = cursor.parent
           
    def rotate_r(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc is not None:
            n.left = gc
            gc.parent = n
        else:
            n.left = None
            
        c.right = n
        n.parent = c
        
        if p is not None:    
            if p.right == n:
                p.right = c
            else:
                p.left = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)
    
    def rotate_l(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc is not None:
            n.right = gc
            gc.parent = n
        else:
            n.right = None
            
        c.left = n
        n.parent = c
        
        if p is not None:
            if p.left == n:
                p.left = c
            else:
                p.right = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
        
        update_height(n)
        update_height(c)              
        
    def rotate_rl(self, n):
        
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc.left and gc.right:
            n.right = gc.left
            c.left = gc.right
            gc.left.parent = n
            gc.right.parent = c
        elif gc.left:
            n.right = gc.left
            gc.left.parent = n
            c.left = None
        elif gc.right:
            c.left = gc.right
            gc.right.parent = c
            n.right = None
        else:
            n.right = None
            c.left = None
            
        gc.left = n
        gc.right = c
        n.parent = gc
        c.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None

        update_height(n)
        update_height(c)
        update_height(gc)        
        
    def rotate_lr(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc.left and gc.right:
            c.right = gc.left
            n.left = gc.right
            gc.left.parent = c
            gc.right.parent = n
        elif gc.left:
            c.right = gc.left
            gc.left.parent = c
            n.left = None
        elif gc.right:
            n.left = gc.right
            gc.right.parent = n
            c.right = None
        else:
            n.left = None
            c.right = None
        gc.left = c
        gc.right = n
        c.parent = gc
        n.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)    
        
    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return None
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return None
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent              
        else:
            return None
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2


def main():

    N = int(input())
    P = map(int, input().split())
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Node:
    def __init__(self,  key=None):
        self.key = key
        self.height = 1
        self.parent = None
        self.left = None
        self.right = None

def get_height(t):
    return 0 if t is None else t.height

def get_balance(t):
    return get_height(t.left) - get_height(t.right)

def update_height(t):
    left_height = get_height(t.left)
    right_height = get_height(t.right)
    if left_height >= right_height:
        t.height = left_height + 1
    else:
        t.height = right_height + 1


class AVL:
    def __init__(self):
        self.root = Node()       
    
    def insert(self, key):
        if self.root.key is None:
            self.root.key = key
            return
        cursor = self.root
        while cursor:
            p = cursor
            if key == cursor.key:
                return
            elif key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        new_node = Node(key)
        new_node.parent = p
        if key < p.key:
            p.left = new_node
        else:
            p.right = new_node
        
        cursor = p
        while cursor:     
            balance = get_balance(cursor)
            if balance == 0:
                break
            elif balance == 2:
                if key < cursor.left.key:
                    self.rotate_r(cursor)
                else:
                    self.rotate_lr(cursor)
                break
            elif balance == -2:
                if key > cursor.right.key:
                    self.rotate_l(cursor)
                else:
                    self.rotate_rl(cursor)
                break
            else:
                update_height(cursor)
                cursor = cursor.parent
           
    def rotate_r(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc is not None:
            n.left = gc
            gc.parent = n
        else:
            n.left = None
            
        c.right = n
        n.parent = c
        
        if p is not None:    
            if p.right == n:
                p.right = c
            else:
                p.left = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)                
    
    def rotate_l(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc is not None:
            n.right = gc
            gc.parent = n
        else:
            n.right = None
            
        c.left = n
        n.parent = c
        
        if p is not None:
            if p.left == n:
                p.left = c
            else:
                p.right = c
            c.parent = p
        else:
            self.root = c
            self.root.parent = None
            
        update_height(n)
        update_height(c)       
      
    def rotate_rl(self, n):
        p = n.parent
        c = n.right
        gc = n.right.left
        
        if gc.left and gc.right:
            n.right = gc.left
            c.left = gc.right
            gc.left.parent = n
            gc.right.parent = c
        elif gc.left:
            n.right = gc.left
            gc.left.parent = n
            c.left = None
        elif gc.right:
            c.left = gc.right
            gc.right.parent = c
            n.right = None
        else:
            n.right = None
            c.left = None
            
        gc.left = n
        gc.right = c
        n.parent = gc
        c.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)

    def rotate_lr(self, n):
        p = n.parent
        c = n.left
        gc = n.left.right
        
        if gc.left and gc.right:
            c.right = gc.left
            n.left = gc.right
            gc.left.parent = c
            gc.right.parent = n
        elif gc.left:
            c.right = gc.left
            gc.left.parent = c
            n.left = None
        elif gc.right:
            n.left = gc.right
            gc.right.parent = n
            c.right = None
        else:
            n.left = None
            c.right = None
        gc.left = c
        gc.right = n
        c.parent = gc
        n.parent = gc
        
        if p is not None:
            if p.left == n:
                p.left = gc
            else:
                p.right = gc
            gc.parent = p
        else:
            self.root = gc
            self.root.parent = None
            
        update_height(n)
        update_height(c)
        update_height(gc)        
        
    def find(self, key):
        cursor = self.root
        while cursor:
            if cursor.key == key:
                return cursor
            if key < cursor.key:
                cursor = cursor.left
            else:
                cursor = cursor.right
        return None
    
    def next_greater_key(self, cursor):
        if cursor is None:
            return None
        if cursor.right:
            cursor = cursor.right
            while cursor.left:
                cursor = cursor.left
            return cursor
        elif cursor.parent.left == cursor:
            return cursor.parent
        elif cursor.parent.right == cursor:
            while cursor.parent and cursor.parent.right == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent
        else:
            return None
        
    def next_smaller_key(self, cursor):
        if cursor is None:
            return None
        if cursor.left:
            cursor = cursor.left
            while cursor.right:
                cursor = cursor.right
            return cursor
        elif cursor.parent.right == cursor:
            return cursor.parent
        elif cursor.parent.left == cursor:
            while cursor.parent and cursor.parent.left == cursor:
                cursor = cursor.parent
            if cursor.parent:
                return cursor.parent              
        else:
            return None
        
    def get_smaller_key(self, key):
        cursor = self.find(key)
        l1 = self.next_smaller_key(cursor)
        l2 = self.next_smaller_key(l1)
        if l2 is None:
            l2 = 0
        else:
            l2 = l2.key
        return l1.key, l2
    
    def get_greater_key(self, key):
        cursor = self.find(key)
        r1 = self.next_greater_key(cursor)
        r2 = self.next_greater_key(r1)
        if r2 is None:
            r2 = 0
        else:
            r2 = r2.key
        return r1.key, r2
                

def main():

    N = int(input())
    P = map(int, input().split())
    
    idx = [-1] * (N + 1)
    for i, v in enumerate(P, 1):
        idx[v] = i
    avl = AVL()
    for i in [0, idx[N], N+1]:
        avl.insert(i)
    total = 0
    for j in range(N - 1, 0, -1):
        n = idx[j]
        avl.insert(n)
        
        l1_idx , l2_idx = avl.get_smaller_key(n)
        l1 = n - l1_idx
        if l1_idx != 0:
            l2 = l1_idx - l2_idx
        else:
            l2 = 0
            
        r1_idx, r2_idx = avl.get_greater_key(n)
        r1 = r1_idx - n
        if r1_idx != N + 1:
            r2 = r2_idx - r1_idx
        else:
            r2 = 0
            
        cnt = (l1 * r2 + r1 * l2) * j
        total += cnt
    
    print(total)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

r = list(range(n))
l = list(range(n))
I = [-1] * (n+1)

for i,P in enumerate(p):
	I[P] = i
#I[1~Nまでの数字] = 0,1,...
#index を求めている
ans  = 0

for N,index in enumerate(I[1:],1):#1からスタート
	L = index -1
	if L >= 0:
		L = l[L]

	R = index + 1
	if  R < n:
		R = r[R]

	l[R-1] = L
	r[L+1] = R
#0 <= L , R < n
	if L >= 0:
		L2 = L-1
		if L2 >= 0:
			L2 = l[L2]
		ans += N * (L-L2) * (R - index)

	if R < n:
		R2 = R+1
		if R2 < n:
			R2 = r[R2]
		ans += N * (index - L ) * (R2 - R)
print(ans)

Submission status: Accepted

Solution code:
class MinSegmentTree():
    def __init__(self, n):
        self.n = n
        self.INF = n - 1
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = min(self.node[2*i + 1], self.node[2*i + 2])

    def get_min(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = min(s, self.node[end])
            if (begin - 1) & 1:
                s = min(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

class MaxSegmentTree():
    def __init__(self, n):
        self.n = n
        self.INF = 0
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = max(self.node[2*i + 1], self.node[2*i + 2])

    def get_max(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = max(s, self.node[end])
            if (begin - 1) & 1:
                s = max(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s


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

ind = {}
for i in range(n):
    ind[a[i]] = i
smax = MaxSegmentTree(n+2)
smin = MinSegmentTree(n+2)

ans = 0
for i in range(n):
    pos = ind[n-i] + 1
    l2 = smax.get_max(0, pos)
    l1 = smax.get_max(0, l2)
    r1 = smin.get_min(pos+1, n+2)
    r2 = smin.get_min(r1+1, n+2)
    smin.update(pos, pos)
    smax.update(pos, pos)
    ans += ((l2 - l1) * (r1 - pos) + (r2 - r1) * (pos - l2)) * (n-i)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,*P = map(int,read().split())

INF = N+100
P = [INF,INF] + P + [INF,INF]

x_to_i = [0] * (INF+1)
for i,x in enumerate(P):
    x_to_i[x] = i

"""
・小さい方から埋めていく。
・埋めた位置に対して、「連結成分の左端」「連結成分の右端」を持つ
・区間の両端については、正しい値が入っている状態を保つ
"""

left = list(range(N+4))
right = list(range(N+4))
filled = [False] * (N+4)

answer = 0
for x,i in enumerate(x_to_i[1:N+1],1):
    filled[i] = True
    L = left[i-1] if filled[i-1] else i
    R = right[i+1] if filled[i+1] else i
    right[L] = R; left[R] = L
    # 自身より大きい場所。左右に2つずつ。
    c = i
    b = L-1; d = R+1
    a = left[L-2]-1 if filled[L-2] else L-2
    e = right[R+2]+1 if filled[R+2] else R+2
    coef = 0
    if b>=2: # 最大値をb,cとして選ぶ
        coef += (b-a)*(d-c)
    if d<=N+1:
        coef += (e-d)*(c-b)
    answer += x*coef

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=input()

#1-indexed
bit=[ 0 for i in range(N+1) ]
bit[0]=None

#BIT
def add(x,w):
	while x<=N:
		bit[x]+=w
		x+=x&(-1*x)

def bitsum(x):
	s=0
	while 0<x:
		s+=bit[x]
		x-=x&(-1)*x
	return s

def search(wa):
	if wa<=0: return 0
	if bitsum(N)<wa: return N+1
	r=N
	l=0
	while r-l!=1:
		m=(l+r)/2
		if bitsum(m)<wa:
			l=m
		else:
			r=m	
	return r


#0-indexed
A=map(int, sys.stdin.readline().split())
#配列のAの数字の位置を1-indexedで格納。例 B[8]=1 は、Aで数字8が配列Aの1番目（1-indexed)にあることを示す
B=[ 0 for i in range(N+1) ]
for i,a in enumerate(A):
	B[a]=i+1

ans=0
#1番大きい数字はBITに追加するだけ
x=N
add(B[x],1)

#2番目に大きい数字から順番に、その数字が2番目に大きい数字として何回カウントされることがあるかをカウント
for x in range(N-1,0,-1):
	cur_p=B[x]	#current position
	cur_v=bitsum(cur_p)
	l1=search(cur_v)
	l2=search(cur_v-1)
	r1=search(cur_v+1)
	r2=search(cur_v+2)
	#print "l2,l1,r1,r2 :: ",l2,l1,r1,r2
	#print "ans+=( (",l1-l2,")*(",r1-cur_p,")+(",cur_p-l1,")*(",r2-r1,") )*",x
	#(左に自分より大きい数字がある場合＋右に自分より大きい数字がある場合)*自分の数字
	ans+=( (l1-l2)*(r1-cur_p)+(cur_p-l1)*(r2-r1) )*x
	#数字をBITに追加
	add(B[x],1)

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=input()

#1-indexed
bit=[ 0 for i in range(N+1) ]
bit[0]=None

#BIT
def add(x,w):
	while x<=N:
		bit[x]+=w
		x+=x&(-1*x)

def bitsum(x):
	s=0
	while 0<x:
		s+=bit[x]
		x-=x&(-1)*x
	return s

def search(wa):
	if wa<=0: return 0
	if bitsum(N)<wa: return N+1
	r=N
	l=0
	while r-l!=1:
		m=(l+r)/2
		if bitsum(m)<wa:
			l=m
		else:
			r=m	
	return r


#0-indexed
A=map(int, sys.stdin.readline().split())
# 配列のAの数字の位置を1-indexedで格納。例 B[8]=1 は、Aで数字8が配列Aの1番目（1-indexed)にあることを示す
B=[ 0 for i in range(N+1) ]
for i,a in enumerate(A):
	B[a]=i+1

ans=0
x=N
add(B[x],1)

#大きい数字から順番に、その数字が2番目に大きい数字として何回カウントされることがあるかをカウント
for x in range(N-1,0,-1):
	cur_p=B[x]	#current position
	cur_v=bitsum(cur_p)
	l1=search(cur_v)
	l2=search(cur_v-1)
	r1=search(cur_v+1)
	r2=search(cur_v+2)
	#print "l2,l1,r1,r2 :: ",l2,l1,r1,r2
	#print "ans+=( (",l1-l2,")*(",r1-cur_p,")+(",cur_p-l1,")*(",r2-r1,") )*",x
	#(左に自分より大きい数字がある場合＋右に自分より大きい数字がある場合)*自分の数字
	ans+=( (l1-l2)*(r1-cur_p)+(cur_p-l1)*(r2-r1) )*x
	#数字をBITに追加
	add(B[x],1)

print ans

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
N=input()

#1-indexed
bit=[ 0 for i in range(N+1) ]
bit[0]=None

def add(x,w):
	while x<=N:
		bit[x]+=w
		x+=x&(-1*x)

def bitsum(x):
	s=0
	while 0<x:
		s+=bit[x]
		x-=x&(-1)*x
	return s

def search(wa):
	if wa<=0: return 0
	if bitsum(N)<wa: return N+1
	r=N
	l=0
	while r-l!=1:
		m=(l+r)/2
		if bitsum(m)<wa:
			l=m
		else:
			r=m	
	return r


#0-indexed
A=map(int, sys.stdin.readline().split())
# 配列のAの数字の位置を1-indexedで格納。例 B[8]=1 は、Aで数字8が1番目（1-indexed)にあることを示す
B=[ 0 for i in range(N+1) ]
for i,a in enumerate(A):
	B[a]=i+1

ans=0
x=N
add(B[x],1)

for x in range(N-1,0,-1):
	cur_p=B[x]	#current position
	cur_v=bitsum(cur_p)
	l1=search(cur_v)
	l2=search(cur_v-1)
	r1=search(cur_v+1)
	r2=search(cur_v+2)
	#print "l2,l1,r1,r2 :: ",l2,l1,r1,r2
	#print "ans+=( (",l1-l2,")*(",r1-cur_p,")+(",cur_p-l1,")*(",r2-r1,") )*",x
	ans+=( (l1-l2)*(r1-cur_p)+(cur_p-l1)*(r2-r1) )*x
	add(B[x],1)

print ans

Submission status: Accepted

Solution code:
N = int(input())
P_id = [0]*(N + 1) # P_id[i]は順列Pに置けるiのindex, P[0]は無視
for index, p in enumerate(map(int, input().split())):
    P_id[p] = index

left_next_index = list(range(- 1, N - 1)) + ['うんこ', - 1] # + [- 1]ではないことに注意, left_next_index[r1] = l1においてr1 = Nの場合があるから
right_next_index = list(range(1, N + 1)) + [N, 'うんこ']

res = 0
for p in range(1, N):
    l1 = left_next_index[P_id[p]]
    l2 = left_next_index[l1]
    r1 = right_next_index[P_id[p]]
    r2 = right_next_index[r1]
    
    res += p*((l1 - l2)*(r1 - P_id[p]) + (P_id[p] - l1)*(r2 - r1))
    
    left_next_index[r1] = l1
    right_next_index[l1] = r1
    
print(res)

Submission status: Accepted

Solution code:
import bisect
import array
N = int(input())
P = list(map(int, input().split()))
P_id = [0]*(N + 1)

for i in range(N):
    P_id[P[i]] = i

A = array.array('i', [- 1, P_id[N], N])


res = 0
for i in range(N - 1, 0, - 1):
    j = bisect.bisect_left(A, P_id[i])
    A.insert(j, P_id[i])
    l1 = A[j - 1]
    r1 = A[j + 1]
    l2 = l1
    r2 = r1
    if l1 != - 1:
        l2 = A[j - 2]
    if r1 != N:
        r2 = A[j + 2]
    
    res += i*((A[j] - l1)*(r2 - r1) + (l1 - l2)*(r1 - A[j]))

print(res)