发现我们可以通过查询 ? 3 i i，来确定 $a_i$ 这个数的值。

然后问题就转变为了求 $\sum_{i=1}^{n} \sum_{j=i}^{n}$ 的值。

直接 st 表加上二分即可。