出處: 2020 NPSC網際網路程式設計大賽高中組初賽pE

殿壬是個天才兒童，他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲，現在要講的是殿壬三歲三個月大時的故事。

這天殿壬在跟他養的貓咪們玩的時候想到了一個有趣的事情。

如果我們先對所有貓咪排成一列，根據他的毛色、個性等等數值算出對每隻貓分別的好感度，再將這些貓咪按照好感度由小到大排序，那麼這個殿壬就稱這個貓咪序列是可愛貓咪序列。

然而對貓咪排序並不是一件簡單的事情。為了怕傷害到那些貓咪，在排序貓咪時唯二能做的操作只有選擇連續的兩隻貓咪或是三隻貓咪，並將牠們的順序反轉。雖然無論哪種操作都不是件省力的事情，但是因為殿壬的貓咪特別喜歡被第二種操作（也就是選擇連續的三隻並反轉的操作），所以殿壬特別喜歡第二種操作，以致於在排序這些貓咪時殿壬都會盡可能的最小化第一種操作的操作次數。

這天，殿壬突發奇想的開始好奇，如果他只想排序某個連續區間的貓咪，那麼他最少所需要的第一種操作次數是多少。當然殿壬是不會被這個問題難倒的，但是為了保險起見，還是請你寫一個程式幫殿壬驗證一下他的答案是不是正確的吧。

輸入格式

輸入的第一行是一個正整數 \(N\)，代表總共有 \(N\) 隻貓咪。

第二行有 N 個正整數 \(a_1, a_2, . . . , a_n\)，代表 \(N\) 隻貓咪依序的好感度。

接下來的 \(Q\) 行，每行會有兩個正整數 \(l, r\)，代表殿壬想要請你幫忙驗算如果想要排序好第 \(l\) 隻貓咪到第 \(r\) 隻貓咪，最少所需要的第一種操作次數是多少。

• \(1 ≤ N, Q ≤ 40000\)
• \(1 \leq a_i \leq 10^9\)，對所有合法的 \(i\)
• \(1 \leq l \leq r \leq N\)，對每一筆殿壬的詢問

輸出格式

對於每一個殿壬問題，請輸出對應的答案。

範例輸入

6
1 5 2 4 3 6
4
1 3
2 4
1 5
3 6

範例輸出

1
1
1
1