首先 kruskal 一下，转化成按照 $a_x$ 排序之后，依次将所有 $i+j=x$ 的 $(i,j)$ 所在的连通块连起来，然后查询有多少有效连边。

一个朴素的想法是，连边完成之后一定满足这一段区间中每个点所在的连通块编号是回文的。所以二分哈希找到每次要连的位置，然后启发式合并修改一下再结合线段树维护哈希值即可做到 $O(n\log^2n)$，不太牛。

考虑进一步利用一下特殊性质，注意到每次要变成回文的区间都是一个前缀或者后缀，我们不妨先只研究前缀。假设之前已经做了三次连边，把 $[1,x],[1,y],[1,z]$ 都连成了回文的，并且满足 $x\lt y\lt z$。先忽略掉 $z$ 后面的部分，就相当于 $[1,z]$ 这个回文串有两个 border 分别是 $x,y$，也就等价于有两个长为 $z-y,z-x$ 的周期。由 WPL 我们知道这等价于有一个长为 $\gcd(z-y,z-x)$ 的周期。所以我们维护当前已知最长的回文前缀 $mx$ 和最小的周期 $t$，而周期由于每次变成原来的约数最多变化 $O(\log n)$ 次，且 $mx$ 变大的时候 $t$ 只会变小。每次加入一个新的回文前缀，如果 $(mx,t)$ 都不变就说明这次没有有效连边，如果 $t$ 变化则暴力所有位置，如果 $mx$ 变化而 $t$ 不变则暴力原 $mx$ 到新 $mx$ 之间的位置，简单分析发现只有 $O(n\log n)$ 次可能的连边。于是就做完了，吗？

我们这样做发现有一个问题，WPL 还有个条件要求 $z-y+z-x\leq z$，但是这个条件并不一定被满足。解决方法非常简单，我们对这些回文串长度倍增分块，第 $i$ 块只维护长度在 $[2^i,2^{i+1})$ 的回文前缀，这样就可以保证 $z-y+z-x\leq z$ 了。分析一下容易发现总复杂度还是 $O(n\log n)$。