TopCoder

User's AC Ratio

76.5% (13/17)

Submission's AC Ratio

16.8% (22/131)

Tags

Description

鳳凰花開,又將到了畢業的季節,為了做為學校生活最後的留念,無論是國小、國中,抑或是高中,都或多或少會製作畢業紀念冊等物品以做紀念。然而其中最重要的要素莫過於「合照」了!大家排成一列,全部入鏡,象徵著眾人的友情永遠存在的紀念照片往往是最珍貴的。

現在,某間學校的學生想要拍設一些合照,有N (1<=N<=50000) 個身高相異的人排隊,然而,由於矮的人不希望被夾在高的人之間(即成「川」字貌XD),因為這樣會有種莫名的壓迫感,因此希望所排的隊形都要能夠不會在任一地方造成「川」字形的狀況。

他們由衷地希望你能幫忙他們排出符合此條件的隊形。

Input Format

第 1 行有一個正整數 N (1<=N<=50000),

之後的 2 ~ n+1 行都有一個正實數 h (1<=h<=1000000)分別代表第 1 個人(即編號為 1的人)到第 n 個人(編號為 n 的人)的身高。

Output Format

對於每一筆測試資料,你都應該要輸出 n+1 行。

第 1 行請輸出一個整數 P 代表「有幾種符合條件的可能」,

之後的 2 ~ n+1 行請你輸出所有可能中「編號字典順序最小」的隊形,

第 1+i 行都應該有一個正整數 ki,代表由左向右數過去第 i 個位置排的是編號 ki的人。

Sample Input

3
170
175
180

Sample Output

4
1
2
3

Hints

範例輸入輸出解釋:

4 種符合條件的可能隊形為
編號 <=> 身高
{1,2,3} <=> {170,175,180}
{1,3,2} <=> {170,180,175}
{2,3,1} <=> {175,180,170}
{3,2,1} <=> {180,175,170}

※2009/02/28:補輸入輸出解釋 - skyly

Problem Source

原TIOJ1512 / Problem Setter: skyly

Subtasks

No. Testdata Range Score
1 0 14
2 1 14
3 2 14
4 3 14
5 4 14
6 5 14
7 6 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 65536 262144 1
1 2000 65536 262144 2
2 2000 65536 262144 3
3 2000 65536 262144 4
4 2000 65536 262144 5
5 2000 65536 262144 6
6 2000 65536 262144 7