#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 5; int n, p[N]; long long ans, mem[N << 1]; int main() { //freopen("book.in", "r", stdin); // freopen("book.out", "w", stdout); scanf("%d", &n); for(int i = 1; i <= n; ++i) scanf("%d", p + i); for(int i = n; i; --i) { memset(mem, 0, sizeof(mem)); int lst = N; mem[N] = i; for(int j = i - 1; j; --j) { if(p[j] > p[i]) ++lst; else --lst; mem[lst] += j; } lst = N; ans += mem[N] * i * p[i]; for(int j = i + 1; j <= n; ++j) { if(p[j] > p[i]) ++lst; else --lst; ans += mem[(N << 1) - lst] * j * p[i]; } } printf("%lld", ans); return 0; }