#include <cstdio> #include <ext/pb_ds/assoc_container.hpp> #include <vector> using namespace std; using i64 = long long; struct IO { #define MAXSIZE (1 << 20) #define isdigit(x) (x >= '0' && x <= '9') char buf[MAXSIZE], *p1, *p2; char pbuf[MAXSIZE], *pp; IO() : p1(buf) , p2(buf) , pp(pbuf) { } ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); } char gc() { if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin); return p1 == p2 ? ' ' : *p1++; } bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; } template <class T> void read(T& x) { double tmp = 1; bool sign = false; x = 0; char ch = gc(); for (; !isdigit(ch); ch = gc()) if (ch == '-') sign = 1; for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0'); if (ch == '.') for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0'); if (sign) x = -x; } void read(char* s) { char ch = gc(); for (; blank(ch); ch = gc()) ; for (; !blank(ch); ch = gc()) *s++ = ch; *s = 0; } void read(char& c) { for (c = gc(); blank(c); c = gc()) ; } void push(const char& c) { if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf; *pp++ = c; } template <class T> void write(T x) { if (x < 0) x = -x, push('-'); // 负数输出 static T sta[35]; T top = 0; do { sta[top++] = x % 10, x /= 10; } while (x); while (top) push(sta[--top] + '0'); } template <class T> void write(T x, char lastChar) { write(x), push(lastChar); } } io; inline int sgn(int x) { return x > 0 ? 1 : (x == 0 ? 0 : -1); } int main() { int n; io.read(n); vector<int> books(n); for (auto& book : books) io.read(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]; } io.write(ans); return 0; }