1017 . C.Node of Sequence
TopCoder
Tags
Description
給你一個整數序列S: s1,s2,...,sn，我們說 si是這個序列的節點(Node)是因為所有在si之前的數 s1,s2,...,si-1都比 si還小，並且所有在si之後的數 si+1,si+2,...,sn都比 si還大。當然s1和sn都不是節點。
給你這樣的一個序列S，請問序列S中有幾個節點？
Input Format
Line 1: 測試資料組數 T (1<=T<=20)
Line 2~N+1:每一列為一組測試資料：第一個數字N (1<=N<=1,000,000) 代表序列S的長度，然後有N個整數s1,s2,...,sn，中間以一個空白間隔。
所有數字的絕對值都不會超過231-1。
Output Format
對於每一筆測試資料，請輸出該序列當中節點(Node)的個數。
Sample Input 1
1
8 1 3 2 4 6 7 5 8
8 1 3 2 4 6 7 5 8
Sample Output 1
1
Hints
範例測資說明：
只有4是節點，因為1,3,2都比4小；6,7,5,8都比4大。
註：
當然對於每一個數字，都可以花O(N)的時間掃描一次整個序列，得到其是否為節點的資訊。
但是這樣下來每筆測試資料執行的時間複雜度達到了O(N2)，似乎有點太慢…
※2007/10/20補註：這個題目如果單純地使用cin的話時間會炸掉，因為輸入資料量太大了！
Problem Source
原TIOJ1017 / Problem Setter: Tmt
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |