TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

75.0% (9/12)

Submission's AC Ratio

16.7% (11/66)

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

For Testdata: 0 ~ 0, Score: 14
For Testdata: 1 ~ 1, Score: 14
For Testdata: 2 ~ 2, Score: 14
For Testdata: 3 ~ 3, Score: 14
For Testdata: 4 ~ 4, Score: 14
For Testdata: 5 ~ 5, Score: 14
For Testdata: 6 ~ 6, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 2000 65536 65536
1 2000 65536 65536
2 2000 65536 65536
3 2000 65536 65536
4 2000 65536 65536
5 2000 65536 65536
6 2000 65536 65536