2008 . 格鬥大賽（Fight）
TopCoder
Description
皇家機器人 AI 格鬥大賽即將開打，根據比賽規則，所有參賽者會被隨機排成一列，然後從左右最鄰近的兩個對手開始對戰。若能打敗左（或右）邊的第一個對手，才能繼續跟左(或右)邊的第二個對手對戰。被分配到最左（或右）邊的參賽者運氣不好，他們一開始就只能往右（或左）邊對戰。
瑞奇是格鬥大賽的主播，他很喜歡預測比賽結果。他會搜集參賽者的資料，評估出參賽者的攻擊指數和防禦指數。他認為只要兩個指數有一個高於對手，而且另一個不低於對手（攻擊指數和攻擊指數相比，防禦指數和防禦指數相比），就能贏得該場戰鬥。
以上面的數據為例，有 9 位參賽者。瑞奇預測 5 號參賽者將可贏得三場勝利：戰勝 4號（5 號的兩個指數皆較高）、3（5 號的攻擊指數較高且防禦指數相同）以及 6（5 號的兩個指數皆較高）的對手。5 號無法戰勝 2 號對手，因為 2 號的防禦指數比 5 號的防禦指數高；同理，5 號無法戰勝 7 號的對手，因為 7 號的攻擊指數比 5 號的攻擊指數高。
根據瑞奇的預測方法，請寫一個程式輸出勝場最多的參賽者會贏幾場。以上面的例子來說，他預測的勝場數為：
因此勝場數最多為 8 場。
Input Format
第一列為一個正整數 N，代表參賽者數。
接下來的 N 列為參賽者資料，第一列為最左邊參賽者的資料，接著依序到最右邊參賽者的資料。每一列有兩個正整數 $a_i$ 和 $d_i$ （$0 \leq a_i , d_i \leq 2 \times 10 ^ {9} , 1 \leq i \leq N $），彼此間以一個空白隔開，分別代表參賽者的攻擊指數和防禦指數。
Output Format
輸出一正整數，為勝場最多的參賽者會贏幾場。
Sample Input 1
9
30 30
60 71
60 65
70 44
80 65
25 25
99 44
100 100
18 19
30 30
60 71
60 65
70 44
80 65
25 25
99 44
100 100
18 19
Sample Output 1
8
Sample Input 2
3
99 4
100 3
98 5
99 4
100 3
98 5
Sample Output 2
0
Hints
Problem Source
2017北市賽(prob 2)
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~10 | $N \leq 100$ | 27 |
| 2 | 11~21 | $N \leq 1000000, a_{i} < a_{i+1}, d_{i} \in \{ 0,1,2,3 \} $ | 27 |
| 3 | 22~43 | $N \leq 1500000$ | 46 |