1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <cstdio>

typedef unsigned int uint;

uint INF = 0xFFFFFFFFU;

template <typename T> T min_of(T a, T b) { return a < b ? a : b; }
template <typename T> T max_of(T a, T b) { return a > b ? a : b; }

inline uint read(uint a, uint b, uint **m) { return a < b ? m[b][a] : (a == b ? 0 : m[a][b]); }
inline void write(uint a, uint b, uint **m, uint v) {
  if (a < b)
    m[b][a] = v;
  else
    m[a][b] = v;
}

bool is_contained(uint a1, uint b1, uint a2, uint b2) { return min_of(a1, b1) <= min_of(a2, b2) && max_of(a2, b2) <= max_of(a1, b1); }

bool is_connected(uint a1, uint b1, uint a2, uint b2) {
  if (a1 == b1) {
    return min_of(a2, b2) < a1 && a1 < max_of(a2, b2);
  } else if (a1 < b1 && a2 >= b2) {
    return a2 > a1 && b2 < b1;
  } else if (a1 > b1 && a2 <= b2) {
    return a2 < a1 && b2 > b1;
  }
  return is_contained(a1, b1, a2, b2) || is_contained(a2, b2, a1, b1);
}

void floyd_warshal(uint N, uint **m) {
  for (uint u = 0; u < N; ++u) {
    for (uint v1 = 0; v1 < N; ++v1) {
      for (uint v2 = 0; v2 < N; ++v2) {
        uint l = read(v1, u, m);
        uint r = read(u, v2, m);
        if (l != INF && r != INF && l + r < read(v1, v2, m)) {
          write(v1, v2, m, l + r);
        }
      }
    }
  }
}

void print(uint N, uint **matrix) {
  for (uint i = 0; i < N; ++i) {
    for (uint j = 0; j < N; ++j) {
      if (read(i, j, matrix) == INF) {
        printf(" _");
      } else {
        printf("%2u", read(i, j, matrix));
      }
    }
    printf("\n");
  }
  printf("\n");
}

int main() {
  uint N;
  scanf("%u", &N);
  uint **matrix = new uint *[N];
  uint *lines = new uint[N];
  for (uint i = 0; i < N; ++i) {
    scanf("%u", &lines[i]);
    lines[i] -= 1;
  }

  for (uint i = 0; i < N; ++i) {
    matrix[i] = new uint[i];
    for (uint j = 0; j < i; ++j) {
      bool con = is_connected(i, lines[i], j, lines[j]);
      matrix[i][j] = con ? 1 : INF;
    }
  }

  // print(N, matrix);
  floyd_warshal(N, matrix);
  // print(N, matrix);

  for (uint i = 0; i < N; ++i) {
    uint s = 0;
    for (uint j = 0; j < N; ++j) {
      uint d = read(i, j, matrix);
      if (d != INF) {
        s += d;
      }
    }
    printf("%u ", s);
  }
  printf("\n");
  return 0;
}