// Arup Guha
// 6/10/2026
// Solution to Kattis Problem: Binary Search Tree
// https://open.kattis.com/problems/bst

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

typedef long long ll;

int main() {

    // My empty map.
    map<int,int> mymap;

    // Get # of nodes.
    int n;
    cin >> n;

    // Initial result.
    ll res = 0;

    // Go through the items.
    for (int i=0; i<n; i++) {

        // Read in the value to be inserted.
        int x;
        cin >> x;

        // Store an iterator above x.
        auto above = mymap.upper_bound(x);

        // Initial setting.
        auto below = above;

        // Special case nothing below.
        if (above == mymap.begin())
            below = mymap.end();

        // One right below it.
        else
            below--;

        // First insert only.
        if (above == mymap.end() && below == mymap.end()) {
            mymap[x] = 0;
        }

        // Only below exists.
        else if (above == mymap.end()) {
            mymap[x] = mymap[(*below).first] + 1;
            res += (mymap[(*below).first] + 1);
        }

        // Only above exists.
        else if (below == mymap.end()) {
            mymap[x] = mymap[(*above).first] + 1;
            res += (mymap[(*above).first] + 1);
        }

        // Now I have both an above and a below.
        else {

            // Get the new depth of this node.
            int newd = max(mymap[(*above).first], mymap[(*below).first]) + 1;
            mymap[x] = newd;
            res += newd;
        }

        cout << res << "\n";
    }

    return 0;
}