#pragma GCC optimize("Ofast,no-stack-protector") #include <cstdio> #include <vector> using namespace std; using i64 = long long; inline int sgn(int x) { return x > 0 ? 1 : (x == 0 ? 0 : -1); } int main() { int n; scanf("%d", &n); vector<int> books(n); for (auto& book : books) scanf("%d", &book); i64 ans = 0; for (int med = 0; med < n; ++med) { vector<i64> sum(n << 1); vector<int> pref(n, sgn(books[0] - books[med])); sum[n] = 1; for (int i = 1; i < n; ++i) { pref[i] = pref[i - 1] + sgn(books[i] - books[med]); if (i <= med) sum[pref[i - 1] + n] += i + 1; } for (int r = med; r < n; ++r) ans += sum[pref[r] + n] * (r + 1) * books[med]; } printf("%lld\n", ans); return 0; }