#pragma GCC optimize("Ofast", "inline", "fast-math", "unroll-loops", "no-stack-protector") #include <cstdio> #include <ext/pb_ds/assoc_container.hpp> #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<int> pref(n, sgn(books[0] - books[med])); __gnu_pbds::cc_hash_table<int, i64> sum; sum[0] = 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]] += i + 1; } for (int r = med; r < n; ++r) ans += sum[pref[r]] * (r + 1) * books[med]; } printf("%lld\n", ans); return 0; }