TopCoder

User's AC Ratio

84.8% (84/99)

Submission's AC Ratio

44.8% (133/297)

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

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 7000 65536 262144 1
1 7000 65536 262144 2
2 7000 65536 262144 3
3 7000 65536 262144 4
4 7000 65536 262144 5
5 7000 65536 262144 6
6 7000 65536 262144 7
7 7000 65536 262144 8
8 7000 65536 262144 9
9 7000 65536 262144 10
10 7000 65536 262144 11