/*
思路
 倒着考虑问题，将原来的序列反向，反向之后挨着去掉最前面的字符，得到的答案根原来的问题是等价的，要求一个字符串的不同的子串的数目
 其实求的就是该字符串所有的后缀的不同的前缀的数量，就是sum{ n - (sa[i]-1) - height[i] }, 对于一个静态不变的字符串，直接用
 这个公式求即可，原来的问题是要不断在字符串末尾添加字符，转换之后就是在翻转的字符串前面依次删除字符，删除最前面的字符其实本质上
 是删掉了一个当前最长的后缀，删掉这个后缀之后，剩下的后缀还是一个字符串的完整后缀集合，所以删掉后缀之后只要能维护住height数组，
 新的height数组就是删掉了头上字符之后剩下那个字符串的height数组，删掉原字符串的第i个后缀，等价于在height数组中将第rk[i]项
 删掉了，一开始整个height是有n项的，删掉一个之后，剩下的height数组中有效数据的相对顺序是不变的，所以用一个链表维护住height数组
 中剩下的值，假设当前排名rk_j的后缀是排名rk[i]的后缀在链表中的后一个，那删除掉第i个后缀，只会影响到height[rk_j]的数值，
 height[rk_j] = min{ height[rk[i]], height[rk_j] }, 这个是后缀数组的性质，所以，删除当前最长的一个前缀，对于height数组
 的更新是O(1)可以维护住的，对于sum{ n - (sa[i]-1) - height[i] }的影响就是扣掉排名rk[i]的后缀对应的 n - (sa[rk[i]]-1) - height[rk[i]]
 , 再扣掉n - (sa[rk_j]-1) - height[rk_j], 再加上height[rk_j]更新之后的 n - (sa[rk_j]-1) - height[rk_j]， 也是O(1)
 的代价就可以更新，最后倒着把答案打印一遍
*/


#include <algorithm>
#include <map>
using namespace std;

const int MAX_STR_LEN = 100005;

int input[MAX_STR_LEN];
int xx[MAX_STR_LEN];
int yy[MAX_STR_LEN];
int c[MAX_STR_LEN];
int sa[MAX_STR_LEN];
int rk[MAX_STR_LEN];
int height[MAX_STR_LEN];
long long ans[MAX_STR_LEN];

int ll[MAX_STR_LEN];        // 链表左指针
int rr[MAX_STR_LEN];        // 链表右指针


class SA {

private:
    const int* S;
    int max_char_val;
    bool sa_flag;
    bool height_flag;
    int str_len;

public:
    // 实际计算的时候，为了方便，字符串下标是从1开始的，所以这里S比str错了一位
    SA(const int* str, int max_char_val, int n) : S(str-1), max_char_val(max_char_val), sa_flag(false), height_flag(false), str_len(n) { }

    int* get_sa() {
        int* x = xx;
        int* y = yy;

        if (sa_flag) {
            return sa;
        }

        int n = str_len, m = max_char_val;

        for (int i = 1; i <= n; i ++ )
            c[x[i] = S[i]] ++ ;

        for (int i = 2; i <= m; i ++ )
            c[i] += c[i - 1];

        for (int i = n; i; i -- )
            sa[c[x[i]] -- ] = i;

        for (int k = 1; k <= n; k <<= 1)
        {
            int num = 0;
            for (int i = n - k + 1; i <= n; i ++ )
                y[ ++ num] = i;

            for (int i = 1; i <= n; i ++ )
                if (sa[i] > k)
                    y[ ++ num] = sa[i] - k;

            for (int i = 1; i <= m; i ++ )
                c[i] = 0;

            for (int i = 1; i <= n; i ++ )
                c[x[i]] ++ ;

            for (int i = 2; i <= m; i ++ )
                c[i] += c[i - 1];

            for (int i = n; i; i -- )
                sa[c[x[y[i]]] -- ] = y[i], y[i] = 0;

            swap(x, y);

            x[sa[1]] = 1, num = 1;
            for (int i = 2; i <= n; i ++ )
                x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;

            if (num == n)
                break;

            m = num;
        }

        for (int i = 1; i <= n; i ++ )
            rk[sa[i]] = i;

        sa_flag = true;
        return sa;
    }

    int* get_rk() {
        if (!sa_flag) {
            get_sa();
        }

        return rk;
    }

    int* get_height() {
        if (height_flag) {
            return height;
        }

        if (!sa_flag) {
            get_sa();
        }

        int n = str_len;

        for (int i = 1, k = 0; i <= n; i ++ )
        {
            if (rk[i] == 1)
                continue;

            if (k)
                k --;

            int j = sa[rk[i] - 1];

            while (i + k <= n && j + k <= n && S[i + k] == S[j + k])
                k ++ ;
            height[rk[i]] = k;
        }

        height_flag = true;
        return height;
    }
};


map<int, int> hh;
int hash_val = 1;
void add_hash(int val) {
    if (hh.find(val) == hh.end()) {
        hh[val] = hash_val++;
    }
}



int main() {
    //freopen("/Users/grh/Programming/CLionProjects/Algorithm/input.txt", "r", stdin);

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &(input[n-1-i]));
        add_hash(input[n-1-i]);
    }

    for (int i = 0; i < n; i++) {
        input[i] = hh[input[i]];
    }

    rr[0] = 1, ll[n+1] = n;
    for (int i = 1; i <= n; i++) {
        ll[i] = i-1, rr[i] = i+1;
    }

    SA algo(input, 100005, n);
    int* sa_arr = algo.get_sa();
    int* h_arr = algo.get_height();
    int* rk_arr = algo.get_rk();

    long long tot = 0;
    for (int i = 1; i <= n; i++) {
        tot += n - (sa[i] - 1) - h_arr[i];
    }
    ans[n-1] = tot;

    for (int i = 1; i<= n-1; i++) {
        // 将第i个后缀删掉
        int rk_i = rk_arr[i];
        int rk_j = rr[rk_i];

        tot -= n - (sa_arr[rk_i] - 1) - h_arr[rk_i];
        tot -= n - (sa_arr[rk_j] - 1) - h_arr[rk_j];
        h_arr[rk_j] = min(h_arr[rk_j], h_arr[rk_i]);
        tot += n - (sa_arr[rk_j] - 1) - h_arr[rk_j];

        ans[n-1-i] = tot;

        rr[ll[rk_i]] = rr[rk_i];
        ll[rr[rk_i]] = ll[rk_i];
        ll[rk_i] = rr[rk_i] = 0;
    }

    for (int i = 0; i < n; i++) {
        printf("%lld\n", ans[i]);
    }

    return 0;
}