UUiuui 說：「我個人認為掃描線就應該拌逆序數對，因為這個 potential function 的度數很容易直接影響到最短路的長度。你往裡砸的時候一瞬間他就會產生大量的單位向量，俗稱 D&C，會嚴重影響題目的複雜度，以至於對整個競程圈，和凸包的怪化。再或者說透過這歐拉定理很容易推斷出人工飼養的希爾伯特，他是可以捕獲野生的 Splay tree，所以說不管這平面圖的割是否具有最小包覆圓，仙人掌的 N 次方是否有 Minkowski sum，都不會影響到 AC 自動機跟扇形併在賽場匯合。」

VVivvi 一點也聽不懂他在說什麼，正當他一臉困惑的時候，ωiωi 跑過來說：「沒錯！掃描線就應該拌逆序數對！」

VVivvi 看到地板上有 $N$ 個點，這些點從 1 到 $N$ 編號，且它們任三點不共線，旁邊還有一根長到你可以視為是無限長的棍子。

ωiωi 想要決定這根棍子初始的角度和位置，並且讓棍子往某個和棍子垂直的固定方向移動，掃過所有的點，將掃過的點的編號按順序記錄下來，再數一數這個序列中有幾個逆序數對。

要是棍子的初始角度、位置或移動方向，會造成棍子無法掃過所有的點，或者存在兩個點會同時被棍子掃過（這樣就不知道要先記錄誰了），那 ωiωi 就會覺得這個初始角度、位置和移動方向的組合是不好的。

ωiωi 請 VVivvi 幫他做這些事，VVivvi 要選擇好的初始角度、位置和移動方向。在 VVivvi 隨意地選擇後，ωiωi 覺得很無聊，因此他問你 $Q$ 個問題，第 $i$ 個問題是：在所有可能的記錄下來的相異序列中，逆序數對的數量第 $k_i$ 大的是多少？

正式地說，令 $S$ 為包含所有可能的記錄下來的序列的集合，請你找出將這個集合中的序列按照其中的逆序數對數量由大到小排序後，第 $k_i$ 個序列中有多少逆序數對。（很明顯地，逆序數對數量相同的序列，排序順序不會影響答案。）

一個序列 $s_1,s_2,\dots,s_N$ 的逆序數對數量是滿足 $1 \leq i < j \leq N$ 且 $s_i > s_j$ 的 $(i,j)$ 數量。

下圖是範例測資一的一些棍子初始角度、位置和移動方向的範例：

所有可能的記錄下來的序列為：

• $\lbrace 3,1,4,2\rbrace$
• $\lbrace 3,4,1,2\rbrace$
• $\lbrace 4,3,2,1\rbrace$
• $\lbrace 4,2,3,1\rbrace$
• $\lbrace 2,4,1,3\rbrace$
• $\lbrace 2,1,4,3\rbrace$
• $\lbrace 1,2,3,4\rbrace$
• $\lbrace 1,3,2,4\rbrace$