TopCoder

User's AC Ratio

88.5% (69/78)

Submission's AC Ratio

46.4% (108/233)

Tags

Description

給定一排牛(不是一牛排)每頭牛的高度,牠們只能往右平視或俯視,請問牠們分別能夠看到幾頭牛?
(如果兩頭牛的高度一樣,那麼左邊的牛的視野只能看到右邊的牛為止。)

Input Format

第一列有正整數N(1<=N<=1,000,000)
第2~N+1列各有一個正整數,依序代表由左而右的牛隻高度。所有數字都會在int範圍。

Output Format

每一列分別輸出一個整數,代表由左而右每頭牛所能看見的牛隻數量。
請注意:最後一列一定會輸出0。

Sample Input

5
1
2
3
4
5

Sample Output

1
1
1
1
0

Hints

※額外的測試中,有60%的測試資料當中的 N<=10,000。

Problem Source

原TIOJ1176 / TIOJ Contest #1020。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 9
For Testdata: 1 ~ 1, Score: 9
For Testdata: 2 ~ 2, Score: 9
For Testdata: 3 ~ 3, Score: 9
For Testdata: 4 ~ 4, Score: 9
For Testdata: 5 ~ 5, Score: 9
For Testdata: 6 ~ 6, Score: 9
For Testdata: 7 ~ 7, Score: 9
For Testdata: 8 ~ 8, Score: 9
For Testdata: 9 ~ 9, Score: 9
For Testdata: 10 ~ 10, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 7000 65536
1 7000 65536
2 7000 65536
3 7000 65536
4 7000 65536
5 7000 65536
6 7000 65536
7 7000 65536
8 7000 65536
9 7000 65536
10 7000 65536