package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func _rightsearch(num int, len int, start int) int {
    if start < 0 || start > len + 1 {
        return -1
    }
    for i := start; i < start + 100000 && i <= hitmax; i++ {
        if p[i] > num {
            return i
        }
    }
    return -1
}

func rightsearch(num int, len int, start int) int {
    right := _rightsearch(num, len, start)
        if right == -1 {
            for j:= revp[num] / 10 + 1; j < len / 10; j++ {
                if used_deci[j] == true {
                    right = _rightsearch(num, len, j * 10)
                    if right != -1 {
                        break
                    }
                }
            }
        }
    return right
}

func _leftsearch(num int, len int, start int) int {
    if start < 0 || start > len + 1 {
        return -1
    }
    for i := start; i > start - 100000 && i >= hitmin; i-- {
        if p[i] > num {
            return i
        }
    }
    return -1
}

func leftsearch(num int, len int, start int) int {
    left := _leftsearch(num, len, start)
        if left == -1 {
            for j:= revp[num] / 10 - 1; j >= 0; j-- {
                if used_deci[j] == true {
                    left = _leftsearch(num, len, (j+1) * 10 - 1)
                    if left != -1 {
                        break
                    }
                }
            }
        }
    return left
}

var p, revp []int
var used_deci []bool

var hitmin, hitmax int

func main() {
    buf := make([]byte, 0)
    sc.Buffer(buf, 4000000)
    sc.Split(bufio.ScanWords)
	n := nextInt()
    p = make([]int, n + 1, n + 1)
    revp = make([]int, n + 1, n + 1)
    used_deci = make([]bool, n/10 + 1, n/10 + 1)

    for i := 1; i <= n; i++ {
        p[i] = nextInt()
        revp[p[i]] = i
    }

    hitmin = revp[n]
    hitmax = revp[n]

    // 最大値にusedを付ける
    used_deci[revp[n]/10] = true

    score := 0
    for i := n - 1; i >= 1; i-- {
        pos := revp[i]

        // 右サーチ
        right := _rightsearch(i, n, pos + 1)
        rightright := -1 
        if right != -1 {
            rightright = _rightsearch(i, n, right + 1)
        }

        if right == -1 {
            right = n + 1
        }
        if rightright == -1 {
            rightright = n + 1
        }

        // 左サーチ
        left := _leftsearch(i, n, pos - 1)
        leftleft := -1
        if left != -1 {
            leftleft = _leftsearch(i, n, left - 1)
        }

        if left == -1 {
            left = 0
        }
        if leftleft == -1 {
            leftleft = 0
        }
        
        //fmt.Println("i : ", i, ", pos : ", pos, ", left : ", left, ", leftleft : ", leftleft, ", right : ", right, ", rightright : ", rightright)

        if right != n + 1 {
            
            // 右スコア加算
            //fmt.Println("右スコア加算 : ", i,",",i * ((pos - left) * (rightright - right)))
            score += i * ((pos - left) * (rightright - right))
        }
        if left != -1 {
            // 左スコア加算
            //fmt.Println("左スコア加算 : ", i,",",i * ((left - leftleft) * (right - pos)))
            score += i * ((left - leftleft) * (right - pos))
        }
        used_deci[pos/10] = true
        if hitmin > pos {
            hitmin = pos
        }
        if hitmax < pos {
            hitmax = pos
        }
    }


    fmt.Println(score)
}

Measured memory_bytes: 2816