N = gets.to_i
P = gets.split.map &:to_i

LU = lambda{|i, start|
	v = P[i]
	return start.downto(0).find{|j|
		v < P[j]
	}||-1
}
RU = lambda{|i, start|
	v = P[i]
	return start.upto(N-1).find{|j|
		v < P[j]
	}||N
}

p N.times.map{|i|
	 l,  r = LU[i, i-1], RU[i, i+1]
	ll, rr = LU[i, l-1], RU[i, r+1]
	P[i] * ((rr-r) + (l-ll) + (r!=N ? (i-l-1)*(rr-r) : 0) + (l!=-1 ? (r-i-1)*(l-ll) : 0))
}.inject(&:+)
