/*
水题， 根据性质做就行， nq不会对答案产生贡献， 那么只算p的贡献就好了

*/

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<iostream>
#define ll long long
#define M 200020
#define mmp make_pair
using namespace std;
int read() {
    int nm = 0, f = 1;
    char c = getchar();
    for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
    for(; isdigit(c); c = getchar()) nm = nm * 10 + c - '0';
    return nm * f;
}
map<int, int> ch[M];
int fa[M], len[M], lst = 1, cnt = 1, n;
ll ans = 0;

void insert(int c) {
    int p = ++cnt, f = lst;
    lst = p;
    len[p] = len[f] + 1;
    while(f && !ch[f][c]) ch[f][c] = p, f = fa[f];
    if(f == 0) fa[p] = 1;
    else {
        int q = ch[f][c];
        if(len[q] == len[f] + 1) fa[p] = q;
        else {
            int nq = ++cnt;
            ch[nq] = ch[q];
            fa[nq] = fa[q];
            len[nq] = len[f] + 1;
            fa[p] = fa[q] = nq;
            while(f && ch[f][c] == q) ch[f][c] = nq, f = fa[f];
        }
    }
    ans += len[p] - len[fa[p]];
}

int main() {
    n = read();
    for(int i = 1; i <= n; i++) {
        insert(read());
        cout << ans << "\n";
    }
    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄