TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (4/4)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式、一歲又六個月時養了可愛的拉不拉多、一歲又十個月時養了可愛的貓咪、兩歲時發明了「吃餅乾」的遊戲,而現在要講的,是殿壬四歲二個月大的故事。

這一天他讓大家了解了他對蝴蝶撲朔迷離的愛好,大家送了一大堆蝴蝶給他,還蠻多的,差不多 $N$ 隻。

殿壬接著把分別這些蝴蝶編號從 $1$ 到 $N$ ,然後大概過了一秒,然後大概又過了一秒,蝴蝶飛走了。

殿壬趕緊把這些蝴蝶趕回來,但是蝴蝶們之間的編號卻亂掉了,不過沒關西。

剛剛殿壬把趕蝴蝶趕回來的時候,學會了一種技能,他要重新把蝴蝶照順序排好,接下來用一維數線來說明。

喔對了而且蝴蝶已經被殿壬嚇得不敢動了,所以蝴蝶不會自己飛走。

現在蝴蝶由左到右,編號為依序$a_1, a_2 ... a_N$。
每一次操作,殿壬可以選擇一個蝴蝶的子序列,在不更動子序列內部相對順序的情況下,將這些蝴蝶移動到最右方
譬如現在蝴蝶編號分別為 $[3, 4, 1, 5, 2]$ ,當殿壬挑選出 $[4, 1, 2]$ 這個子序列後,新的蝴蝶順序就會變成 $[3, 5, 4, 1, 2]$ 。

想有揮舞蝴蝶的能力嗎,那有點難,你可以從猜出殿壬花了幾個步驟把蝴蝶重新排成 $[1, 2, ..., N]$ 先做起。
(提示:由於殿壬是個天才兒童,他花的操作數一定是最少的,你只需要最小化操作數,不需要最小化每次操作所選的子序列長度)

Input Format

輸入第一行有一個正整數 $N$ ,代表蝴蝶的數量。
輸入第二行有 $N$ 個正整數 $a_i$ 代表第 $i$ 隻蝴蝶的編號。

  • $1 \leq N \leq 100000$
  • $1 \leq a_i \leq N$

保證每隻蝴蝶的編號互不相同

Output Format

請在第一行輸出將蝴蝶排好的最小操作數 $S$ ,接下來共輸出 $S$ 行。
每一行第一個數字輸出該次操作所選擇的子序列長度,後面接著輸出選擇子序列的數值,可以按照任意順序輸出。

Sample Input

5
3 4 1 5 2

Sample Output

1
3 3 4 5

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~36 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 1
6 1000 65536 262144 1
7 1000 65536 262144 1
8 1000 65536 262144 1
9 1000 65536 262144 1
10 1000 65536 262144 1
11 1000 65536 262144 1
12 1000 65536 262144 1
13 1000 65536 262144 1
14 1000 65536 262144 1
15 1000 65536 262144 1
16 1000 65536 262144 1
17 1000 65536 262144 1
18 1000 65536 262144 1
19 1000 65536 262144 1
20 1000 65536 262144 1
21 1000 65536 262144 1
22 1000 65536 262144 1
23 1000 65536 262144 1
24 1000 65536 262144 1
25 1000 65536 262144 1
26 1000 65536 262144 1
27 1000 65536 262144 1
28 1000 65536 262144 1
29 1000 65536 262144 1
30 1000 65536 262144 1
31 1000 65536 262144 1
32 1000 65536 262144 1
33 1000 65536 262144 1
34 1000 65536 262144 1
35 1000 65536 262144 1
36 1000 65536 262144 1