TopCoder

User's AC Ratio

97.2% (104/107)

Submission's AC Ratio

55.2% (164/297)

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
8 1 3 2 4 6 7 5 8

Sample Output

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

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536