#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll; using namespace std; #ifdef LOCAL #define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl; #else #define debug(x) ; #endif #define mod 1000000007 //1e9+7(prime number) #define INF 1000000000 //1e9 #define LLINF 2000000000000000000LL //2e18 #define SIZE 200010 /* Binary Indexed Tree(1-index) */ struct BIT{ typedef int Type; int bit_size; vector data; BIT(int n){ bit_size = n; data.assign(n+2, 0); } //add x to kth value void add(int k, Type x){ k++; while(k <= bit_size){ data[k] += x; k += k & (-k); } } //sum of [1,k] Type query(int k){ k++; Type rec = 0; while(k > 0){ rec += data[k]; k -= k & (-k); } return rec; } }; vector tree[SIZE]; vector euler; int pos_in[SIZE], pos_out[SIZE]; void dfs(int now){ euler.push_back(now); pos_in[now] = euler.size() - 1; for(int to : tree[now]){ dfs(to); } euler.push_back(now); pos_out[now] = euler.size() - 1; } int main(){ int n; scanf("%d", &n); for(int i=1;i=0;i--){ int res = bit.query(pos_out[i]) - bit.query(pos_in[i]); ans += res; bit.add(pos_in[i], 1); } cout << ans << endl; return 0; }