#include <iostream> #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() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; cin >> n; vector<int> books(n); for (auto& book : books) cin >> book; i64 ans = 0; for (int med = 0; med < n; ++med) { vector<int> pref(n, sgn(books[0] - books[med])); __gnu_pbds::gp_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]; } cout << ans << '\n'; return 0; }