#include <bits/stdc++.h> using namespace std; const int K = 1000001; int n; int a[1000005], tree[1000005]; void add(int x, int c) { for (int i = x; i <= K - 1; i += i & -i) { tree[i] = min(tree[i], c); } } int query(int x) { int ans = 0x3f3f3f3f; for (int i = x; i; i -= i & -i) { ans = min(ans, tree[i]); } return ans; } long long cnt = 0; int main() { //freopen("height.in", "r", stdin); //freopen("height.out", "w", stdout); scanf("%d", &n); memset(tree, 0x3f, sizeof(tree)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); int ns = query(K - a[i] - 1); if (ns != 0x3f3f3f3f) cnt += i - ns; add(K - a[i], i); } printf("%lld\n", cnt); }