N,*P = `dd`.split.map &:to_i
Q = [N+1, *P, N+1]

def scan(ps, ref = nil)
  rs = []
  ps.each_with_index{ |q,i| # 6,7
    j = ref ? (ref[i] ? ref[i]-1 : nil) : i-1 # 2
    prev = j ? ps[j] : nil # 2
    if !prev
      rs << nil
    else
      while j do
        if ps[j] > q
          break
        end
        j = ref ? ref[j] : rs[j]
      end
      rs << j
    end
  }
  rs
end

L1 = scan(Q)
L2 = scan(Q, L1)
R1 = scan(Q.reverse)
R2 = scan(Q.reverse, R1)
L1.map!{ |i| i ? [i-1,-1].max : nil }
L2.map!{ |i| i ? [i-1,-1].max : nil }
R1.reverse!.map!{ |i| i ? [N-i,N].min : nil }
R2.reverse!.map!{ |i| i ? [N-i,N].min : nil }
#p Q[1...-1],L1[1...-1],L2[1...-1],R1[1...-1],R2[1...-1]

p (0...N).reduce(0){ |a,i|
  vl = (L1[i+1] - L2[i+1]) * (R1[i+1] - i)
  vr = (L1[i+1] - i) * (R1[i+1] - R2[i+1])
  #p [i,Q[i],vl,vr]
  a + P[i]*(vl+vr)
}