思路：每个加入一个字符，它对总体本质不同子串的贡献就是$maxlen[now]-maxlen[link[now]]$,还有就是这里的儿子范围分散，转移数组用map。

ll ans;
struct Suffix_Automata {//minlen[i]=maxlen[link[i]]+1;int maxlen[N << 1], link[N << 1], A[N << 1], tmp[N << 1],num[N<<1], Size, Last;map<int, int> trans[N << 1];//儿子很多时用map离散void init(){Size = Last = 1;//memset(trans, 0, sizeof trans);}void Qsort() { //A[],排出一个按照 maxlen 从小到大的结点序列//num[],每个endpos[st]集合的大小for(int i = 1; i <= Size; i ++) tmp[maxlen[i]]++; for(int i = 1; i <= Size; i ++) tmp[i] += tmp[i - 1]; for(int i = 1; i <= Size; i ++) A[tmp[maxlen[i]]--] = i;for (int i =Size; i >= 1; i--) num[link[A[i]]] += num[A[i]];} inline void Extend(int id) {int cur = (++Size), p;num[cur] = 1;maxlen[cur] = maxlen[Last] + 1;for (p = Last; p && !trans[p][id]; p = link[p]) trans[p][id] = cur;//对suffix_path(u->s)所有满足条件的节点加上转移到当前状态的剪头if (!p) link[cur] = 1;//情况1：suffixlink直接到初始化状态   else {int q = trans[p][id];if (maxlen[q] == maxlen[p] + 1) link[cur] = q;//特殊情况2else {//一般情况3int clone = (++Size);//拆一个状态出来maxlen[clone] = maxlen[p] + 1;trans[clone] = trans[q];//memcpy(trans[clone], trans[q], sizeof trans[q]);link[clone] = link[q];for (; p && trans[p][id] == q; p = link[p]) trans[p][id] = clone;link[cur] = link[q] = clone;}}ans = ans + maxlen[cur] - maxlen[link[cur]];Last = cur;}
}sam;
int a[N];
int main()
{//freopen("in.txt", "r", stdin);int n = in();f(i, 1, n)a[i] = in();sam.init();f(i, 1, n){sam.Extend(a[i]);printf("%lld\n", ans);}return 0;
}