C++ :

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int a[100002];
int v[100002];
int p[100002];

struct Node {
	Node *nxt;
	int id;
} nodes[100002], *head;

int main() {
	//freopen("alice.in", "r", stdin);
	//freopen("alice.out", "w", stdout);
	int n;
	scanf("%d", &n);
	head = NULL;
	for (int i=1; i<=n; ++i) {
		scanf("%d", a+i);
		nodes[i].id = i;
		p[a[i]] = i;
		if (a[i]==1) {
			nodes[i].nxt = head;
			head = nodes + i;
		} else {
			nodes[i].nxt = nodes[p[a[i]-1]].nxt;
			nodes[p[a[i]-1]].nxt = nodes + i;
		}
	}
	int tmp_v = 1;
	while (head!=NULL) {
		v[n-head->id+1] = tmp_v++;
		head = head->nxt;
	}
	//  for (int i=1; i<=n; ++i)
	//    fprintf(stderr, "%d\n", v[i]);
	int l = 1, r = 1;
	long long ans = 0ll;
	for (int i=1; i<=n; ++i) {
		int index = lower_bound(p+l, p+r, v[i])-p;
		ans += index;
		p[index] = v[i];
		if (index==r) ++r;
	}
	printf("%lld\n", ans);
	return 0;
}