2201 . 糖豆人改（Fallguys）
TopCoder
Tags
Description
最近流行一款新推出的遊戲《糖豆人：終極淘汰賽》(Fall Guys: Ultimate Knockout)，這是一款大型派對遊戲，遊戲中會有許多不同種類的關卡，每一輪的關卡都是隨機決定的，而在一輪中會淘汰數量不等的玩家，玩家需要一步步晉級闖關直到留下最後一名獲勝者。
一場遊戲會有很多輪，在每一輪遊戲開始時，所有的玩家會排成一排，每一位玩家都會有一個能力值，不會有任兩個玩家的能力值重複。而雪花菈米發現了遊戲的一個小訣竅，當一個人的能力值比自己相鄰玩家的能力值都還要高的話，那麼該玩家就會晉級，否則該玩家就會被淘汰。
現在給你一整排 $N$ 位遊戲玩家的排列方式，並且進行 $Q$ 場遊戲，第 $i$ 場遊戲會挑出區間 $[l_i,r_i]$ 的玩家進行遊戲，而在遊戲完成後，玩家無論是否被淘汰都會回到原本的位置（也就是說，每場遊戲獨立）。請問對於每一場遊戲，要進行幾輪遊戲才可以有人獲勝？
Input Format
首行輸入兩個正整數 $N,Q$，代表這場遊戲有幾個玩家。
接下來一行有 $N$ 個正整數 $p_i$，代表一開始遊戲玩家的排列方式。
接下來 $Q$ 行，每一行有兩個正整數 $l_i,r_i$，代表第 $i$ 場遊戲決定要挑出區間 $[l_i,r_i]$ 的玩家進行遊戲。
Output Format
輸出 $Q$ 行，第 $i$ 行一個整數，代表第 $i$ 場遊戲要獲勝所需的場數(淘汰到剩下最後一人所需的場數)。
Sample Input 1
5 3
9 5 10 1 6
1 5
2 3
2 5
9 5 10 1 6
1 5
2 3
2 5
Sample Output 1
2
1
2
1
2
Sample Input 2
10 4
7 2 19 13 18 6 16 3 9 17
1 1
1 10
1 8
1 2
7 2 19 13 18 6 16 3 9 17
1 1
1 10
1 8
1 2
Sample Output 2
0
3
2
1
3
2
1
Hints
測資限制：
- $1\le N, Q\leq 5\times 10^ 5$。
- $1\le p_i\leq 10^ 9$。
- 不會有任兩個玩家的能力值重複。
本題共有 $4$ 組測試題組，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。
- ($8\%$) $N,Q\le 3000$。
- ($31\%$) $l_i=1$。
- ($25\%$) $N,Q\le 10^ 5$。
- ($36\%$) 無額外限制。
Problem Source
2021 板中TOI模考模擬賽
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 2~15 | $N,Q\le 3000$。 | 8 |
| 2 | 16~27 | $l_i=1$。 | 31 |
| 3 | 2~15, 28~41 | $N,Q\le 10^ 5$。 | 25 |
| 4 | 0~55 | 無額外限制。 | 36 |