rt

https://www.luogu.com.cn/record/201219511

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

const int MAXN = 2e5 + 7;
char a[MAXN];

vector<int> sa;

bool check(int x, int y)
{
	if (x >= sa.size()) return true;
	x = sa[x];
	while (x && y && a[x] == a[y]) x--, y--;
	return a[x] > a[y];
}

int height(int idx)
{
	int l = 0, r = 0;
	if (idx) {
		int x = sa[idx - 1], y = sa[idx];
		while (x && y && a[x] == a[y]) x--, y--, l++;
	}
	if (idx != sa.size() - 1) {
		int x = sa[idx], y = sa[idx + 1];
		while (x && y && a[x] == a[y]) x--, y--, r++;
	}
	return max(l, r);
}

signed main()
{
	int n, ans = 0; cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		int l = 0, r = i;
		while (l < r)
		{
			int mid = l + r >> 1;
			if (check(mid, i)) r = mid;
			else l = mid + 1;
		}
		sa.insert(sa.begin() + l, i);
		ans += (i - height(l));
		cout << ans << '\n';
	}
}