//Jackson Simoneau
//COP 3503H - Fall 2026
//K1: Binary Search Tree

import java.util.*;
public class bst {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();

        //initialize set to track inserted values
        TreeSet<Integer> set = new TreeSet<>();
        int depth[] = new int[n+1];
        long res = 0;

        for(int i = 0; i < n; i++) {
            int x = input.nextInt();

            //find the previous and next elements that have been inserted
            //one of these will be the child of the other, so d = 1 + [deeper node]
            int d = 0;
            if(set.lower(x) != null) d = Math.max(d, 1+depth[set.lower(x)]);
            if(set.ceiling(x) != null) d = Math.max(d, 1+depth[set.ceiling(x)]);

            //update total and add x to set
            depth[x] = d;
            res += d;
            set.add(x);

            System.out.println(res);
        }
    }
}