using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
using System.Text;//テキストの高速出力に必要
class Program
{
static int n = int.Parse(Console.ReadLine());
static long[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
static long[] numPositions = new long[n];//各数字の場所
static long[] bits = new long[n+1];
static long aimPos = 0;

	static void Main()
	{
    long posL = 0;
    long posLL = 0;
    long posR = n+1;
    long posRR = n+1;
    long answer = 0;
  
    for(int i = 0; i < n; i++)
    {
      numPositions[nums[i]-1] = i;
    }

    bits = BitAdd(bits, numPositions[n-1]+1, 1);
    for(int i = 0; i < n-1; i++)
    {
      long positionCount = 0;

      aimPos = numPositions[n-2-i]+1;
      posL = Search(0,numPositions[n-2-i],-1);
      if(posL > 0)
      {
        aimPos = posL;
        posLL = Search(0,posL-1,-1);
      }

      aimPos = numPositions[n-2-i]+1;
      posR = SearchB(numPositions[n-2-i]+1,n+1,1);
      if(posR < n+1)
      {
        aimPos = posR;
        posRR = SearchB(posR+1,n+1,1);
      }

      aimPos = numPositions[n-2-i]+1;
      //Console.WriteLine(i+" "+posLL+" "+posL+" "+posR+" "+posRR);
      if(posL > 0)
      {
        positionCount += (posL - posLL)*(posR - aimPos);
        //Console.WriteLine(i+" "+positionCount+"l");
      }
      if(posR < n+1)
      {
        positionCount += (aimPos - posL)*(posRR - posR);
        //Console.WriteLine(i+" "+positionCount+"r");
      }

      bits = BitAdd(bits, numPositions[n-2-i]+1, 1);
      //Console.WriteLine(i+" "+(numPositions[n-2-i]+1)+"b");
      answer += positionCount * (n-1-i);
    }

		Console.WriteLine(answer);
	}

  static long[] BitAdd(long[] bits, long i, long x)//BITでiだけにx加算。O(logn)
  {
    int n = bits.Length-1;
    while(i <= n)
    {
      bits[i] += x;
      i += i&-i;
    }
    return bits;
  }

  static long BitSum(long[] bits, long i)//BITでi以下の総和を計算。O(logn)
  {
    long sum = 0;
    while(i > 0)
    {
      sum += bits[i];
      i -= i&-i;
    }
    return sum;
  }

  static long Search(long min, long max, int MinorMax)//二分探索法で最小値-1最大値1を求める
  {
    while (true)
    {
      long mid = min + (max - min) / 2;
      if(MinorMax == 1)
      {
        if(Check(mid)) min = mid;//さらに大きくても成り立つかも
        else max = mid;
      }else
      {
        if(Check(mid)) max = mid;//さらに小さくても成り立つかも
        else min = mid;
      }

      if(max - min <= 1)
      {
        if(MinorMax == 1)
        {
          if(Check(max)) return max;//最大値で成り立つかの確認を優先
          else return min;
        }else
        {
          if(Check(min)) return min;//最小値で成り立つかの確認を優先
          else return max;
        }

      break;
      }  
    }
  }

  static bool Check(long testNum)
  {
    //Console.WriteLine(testNum);
    if(BitSum(bits,aimPos-1) - BitSum(bits,testNum) == 0) return true;
    return false;
  }  

  static long SearchB(long min, long max, int MinorMax)//二分探索法で最小値-1最大値1を求める
  {
    while (true)
    {
      long mid = min + (max - min) / 2;
      if(MinorMax == 1)
      {
        if(CheckB(mid)) min = mid;//さらに大きくても成り立つかも
        else max = mid;
      }else
      {
        if(CheckB(mid)) max = mid;//さらに小さくても成り立つかも
        else min = mid;
      }

      if(max - min <= 1)
      {
        if(MinorMax == 1)
        {
          if(CheckB(max)) return max;//最大値で成り立つかの確認を優先
          else return min;
        }else
        {
          if(CheckB(min)) return min;//最小値で成り立つかの確認を優先
          else return max;
        }

      break;
      }  
    }
  }

  static bool CheckB(long testNum)
  {
    //Console.WriteLine(testNum);
    if(BitSum(bits,testNum-1) - BitSum(bits,aimPos) == 0) return true;
    return false;
  } 
  
}

Measured memory_bytes: 20308