#include <stdio.h>
#include <vector>
using namespace std;
#define MN 100005
typedef long long ll;
int n, x, c[MN];
vector <int> v[MN];
ll pairans, distans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) c[i] = i, v[i].push_back(i);
for (int k = 1; k < n; k++) {
scanf("%d", &x);
ll X = (ll)(v[c[x]].size());
ll Y = (ll)(v[c[x + 1]].size());
pairans += X * Y;
distans += Y*(Y + 1) / 2LL * X + (X - 1)*X / 2LL * Y;
if (X > Y) {
int C = c[x + 1];
for (int i = v[C].size(); i--;) {
int a = v[C][i];
c[a] = c[x];
v[c[x]].push_back(a);
}
v[C].clear();
}
else {
int C = c[x];
for (int i = v[C].size(); i--;) {
int a = v[C][i];
c[a] = c[x + 1];
v[c[x + 1]].push_back(a);
}
v[C].clear();
}
printf("%lld %lld\n", pairans, distans);
}
}
