object Solution {

  def solve(A: Array[Int]): Int = {
    def stopLimit(x: Int): Boolean = x >= (Math.pow(10,9) + 7)
    def S(a: Array[Int]): Array[Int] = {
      go(0, a.length - 1, 0, Nil, a).toArray
    }

    def max(sub_i: Int, sub_j: Int, a: Array[Int]): Int = {
      def go(i: Int, j: Int, max: Int): Int = {
        def getMax(i: Int) = if (a(i) > max) a(i) else max
        if (i == j)
          getMax(i)
        else
          go(i + 1, j, getMax(i))
      }
      go(sub_i, sub_j, 0)
    }
    def iLimit(k: Int, a: Array[Int]) = a.size - k - 1
    def j(i: Int, k: Int) = i + k

    def goI(k: Int, i: Int, iLimit: Int, b: List[Int], a: Array[Int]): List[Int] = {
      if ( i == iLimit || stopLimit(b.size))
        max(i,j(i, k),a) :: b
      else
        goI(k, i+1, iLimit, max(i,j(i,k), a) :: b, a)
    }

    def go(k: Int, kLimit: Int, i: Int, b:List[Int], a:Array[Int]): List[Int] = {
      if (k == kLimit) {
        val r = goI(k, i, iLimit(k,a), b, a)
        r
      } else {
        val goIr = goI(k, i, iLimit(k,a), b, a)
        go(k+1, kLimit, i, goIr, a)
      }
    }
    val sa = S(A)
    val ssa = S(S(A).reverse)
    ssa.foldLeft(0)(_ + _)
  }

    def main(args: Array[String]) {
        val sc = new java.util.Scanner (System.in);
        var n = sc.nextInt();
        var a = new Array[Int](n);
        for(a_i <- 0 to n-1) {
           a(a_i) = sc.nextInt();
        }
        val result = solve(a);
        println(result)
    }
}