#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, a[N], last[N];
int deg[N];

vector<int> g[N];

void addedge(int u, int v) {
    g[u].push_back(v), ++deg[v];
}

queue<int> q;
int num, pos[N];

int c[N];

int lowbit(int x) { return x & -x; }

void update(int x, int v) {
    while (x <= n) {
        c[x] = max(c[x], v);
        x += lowbit(x);
    }
}

int ask(int x) {
    int res = 0;
    while (x) {
        res = max(res, c[x]);
        x -= lowbit(x);
    }
    return res;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        if (a[i] != 1) addedge(last[a[i] - 1], i);
        if (last[a[i]]) addedge(i, last[a[i]]);
        last[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) if (!deg[i]) q.push(i);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        pos[x] = ++num;
        for (int i = g[x].size() - 1; i >= 0; --i) {
            int y = g[x][i];
            if (--deg[y] == 0) q.push(y);
        }
    }
    long long ans = 0;
    for (int i = n, tmp; i; --i) tmp = ask(pos[i] - 1) + 1, update(pos[i], tmp), ans += (long long)tmp;
    cout << ans << endl;
    return 0;
}