5647. sha7dow loves sqrt technology

$\texttt{sha7dow}$ 很喜欢根号复杂度的算法，在学习莫队二次离线时找到了区间逆序对的模板题。

给你一个长为 $\textit{n}$ 的序列 $\textit{a}$，$\textit{m}$ 次询问，每次查询一个区间的逆序对数。
$\textit{1} \leqslant \textit{n,m} \leqslant \textit{10}^{\textit{5}}$，$\textit{0} \leqslant \textit{a}_{\textit{i}} \leqslant \textit{10}^{\textit{9}}$。

$\texttt{sha7dow}$ 学习了整整一天才通过了这道模板题，所以他也想考考你，但没有数据的他打算用一种简单的方式生成所有查询的区间。

• 生成一个队列，队列中只有一个区间 $[1,n]$。
• 不断取出队列的第一个区间，直到队列为空。
• 若这个区间长度不为 $1$，则作为一个查询的区间 $S_i$，并以某种方式拆分成按左端点从小到大排序的若干个区间 $T_{i,j}$ 后全部放回队列中。

$\texttt{sha7dow}$ 发现这种生成方式似乎过于简单，所以对于每个区间 $S_i$，你还需要求出所有满足 $j_1<j_2$ 且 $j_1, j_2$ 奇偶性不同的 $T_{i,j_1}, T_{i,j_2}$ 拼接形成的序列的逆序对数之和。