這個世界上有很多異常的物體，統稱 $\text{SCP}$ (原因是有一個會收容異常的基金會叫 $\text{SCP}$ 基金會)，但是想要成為一個 $\text{SCP}$ 沒有這麼容易，需要好好學習一個異常需要會的知識和技能，最後還要在 $\text{SCP}$ 大學考試考到 $\text{A}$ 級的成績才能錄取。

考到 $\text{SCP}$ 大學是每個青少年異常的夢想，只是有些異常不知該如何學習異常知識，這時就有業者來開班了，「$\text{SCP - A}$ 特訓班，讓你在眾多異常裡脫穎而出，保證考 $\text{A}$ 級，現在報名即可享 $888$ 折優惠！」

不只這樣，還有附歷屆學員的心得：「自從報名了這個班，別人看到我都會嚇得眼睛都不敢眨呢！」學號為 $173$ 的學員說道，「上了這個班以後，我連強酸都不怕了！」學號為 $682$ 的學員說道。

$\text{Hehe}$ 怪在看到 $\text{SCP - A}$ 特訓班後，就跑去報名了。第一堂課的老師是 【▅﹌€＄﹌，他自稱在業界多年，懂很多大家不知道的知識。首先，他給大家講解了一個異常例題：在第一天有 $a$ 個異常，在第二天有 $b$ 個異常，之後每一天的異常數量會是前兩天異常數量的加總，那在第 $k$ 天有幾個異常呢 ($k ≤ 10 ^{18}$)？有同學說可以矩陣快速冪，老師說其實只要存 $k≤12$ 的答案就好了，因為在他的經驗中，$k$ 根本不會到 $10^{18}$ 那麼大。$\text{Hehe}$ 怪覺得很崇拜，老師竟然懂這麼多東西，結果這時有同學說：「老師我在 $\text{SCP}$ 列表裡沒有看到你，你是不是根本沒通過 $\text{SCP}$ 考試！」老師回答：「我的經驗比你豐富多了，我才不屑教你這種 $\frac{1}{2}$ 瓶 $H_{2\ }O$ 的 Macaca cyclopis！你們一小時只要付我 $\frac{sin(1.56979633)}{cos(1.56979633)}$ 元，雖然我不是數學家，但這聽起來還不錯對吧！」

之後老師講解到了一個例題，有一個 $1\sim n$ 的排列 $a_1\sim a_n$，一個 $1\sim n$ 的環狀排列 $c_1\sim c_n$ ($1\sim n$ 的排列的定義是將 $1\sim n$ 的元素經過任意次交換得到的序列，環狀則是將其頭尾相連，可參考圖片)，$a$ 和 $c$ 在相同的數字間有感應器，比方說如果 $a_i = c_j = x$，那在按下 $a_i$ 後，$c_j$ 就會亮起來。我們定義一個連續亮燈序列為：在環狀排列 $c$ 上，任何一個亮起來的元素都可以通過若干個亮起來的元素，到達任意一個亮起來的元素。

以下為 $n=6$，$c_1\sim c_n = \{2,5,6,3,1,4\}$ 的序列，圖一、二、三為連續亮燈序列，圖四卻不是 (黃色的格子為有亮燈的格子)：

題目要問的是有多少組 $(l,r)$ 數對 ($1≤l≤r≤n$)，在把 $a_l\sim a_r$ 都按下去後，在 $c$ 上會形成一個連續亮燈序列。

這題的 $n≤10^5$，老師說可以枚舉 $l,r$，再看看形成的序列合不合法，$O(n^3)$ 搞定。有同學跟老師說這樣太慢了，老師說他自己測範例測資一下子就算出答案了，要大家不准質疑他。

現在是輪到 $\text{Hehe}$ 怪的實作時間，請異常聰明你幫他邁向 $\text{A}$ 級之路吧！如果能把 $O(n^3)$ 變得更小，那他會很感謝你的！