시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 181 76 43 43.434%

문제

크기 n의 순열은, 1부터 n까지의 정수가 정확히 한 번 등장하는 길이 n의 수열을 뜻한다. 이 순열을 a1, a2, ..., an 으로 표기하자. 순열 a를 통해서 순열 그래프를 만들 수 있다. 순열 그래프는 1, 2, ..., n의 번호를 가진 n개의 정점으로 이루어진 무방향 그래프이다. 순열 그래프의 두 정점 쌍 i, j (1 ≤ i < j ≤ n) 는 ai > aj 일때 간선으로 연결되어 있다.

순열 그래프의 연결성을 판별하기 위해서, 당신은 순열 그래프를 다음과 같은 알고리즘으로 탐색해야 한다.

  1. 1번 정점부터 순서대로 n번 정점까지 순회한다. 현재 처리 중인 정점을 i 번 정점이라고 하자.
  2. i번 정점이 이전에 탐색되었다면, 넘어간다. 그렇지 않다면, i번 정점과 연결된 모든 정점을 탐색한 후, 탐색한 정점을 모아 집합을 하나 만든다.
  3. 최종적으로, 구한 집합의 총 개수와, 각 집합의 정보를 출력한다.

알고리즘을 읽은 동욱이는, 이 문제가 그래프의 연결 컴포넌트를 구하는 쉬운 문제임을 알게 되었다. 동욱이는 재현이에게 ”이거 깊이 우선 탐색으로 풀면 돼?” 라고 물었다. 재현이는 아무 대답도 하지 않았다. 당신은 어떻게 생각하는가?

입력

첫번째 줄에 순열의 길이 n (1 ≤ n ≤ 1, 000, 000)이 주어진다.

두번째 줄에 n개의 공백으로 구분된 정수가 주어진다. 순열의 원소 a1, a2, ..., an 을 뜻한다.

출력

첫번째 줄에 구한 집합의 개수 m을 출력한다.

이후 m개의 줄에 걸쳐 각각의 집합을 출력한다. 첫번째로 집합의 크기 si를 출력하고, 이후 그 집합에 속한 si개의 정점의 번호를 공백으로 구분하여 출력한다. 정점의 번호는 오름차순으로 출력한다.

여러 개의 집합을 출력할 때, 집합에 속한 가장 작은 번호의 정점을 기준으로 오름차순으로 출력하라.

예제 입력 1

4
2 3 1 4

예제 출력 1

2
3 1 2 3
1 4

힌트

예제의 순열 그래프를 그리면 다음과 같다.

W3sicHJvYmxlbV9pZCI6Ijc5ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzVmMFx1YWNiMFx1YzEzMSBcdWQzMTBcdWJjYzQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDA2Y1x1YWUzMCBuXHVjNzU4IFx1YzIxY1x1YzVmNFx1Yzc0MCwgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTVjIFx1YmM4OCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWIyOTQgXHVhZTM4XHVjNzc0IG5cdWM3NTggXHVjMjE4XHVjNWY0XHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YzIxY1x1YzVmNFx1Yzc0NCBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj4gXHVjNzNjXHViODVjIFx1ZDQ1Y1x1YWUzMFx1ZDU1OFx1Yzc5MC4gXHVjMjFjXHVjNWY0IGFcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1YzIxY1x1YzVmNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWI5N2MgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzIxY1x1YzVmNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWIyOTQgMSwgMiwgLi4uLCBuXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMDBcdWM5YzQgblx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YmIzNFx1YmMyOVx1ZDVhNSBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NzRcdWIyZTQuIFx1YzIxY1x1YzVmNCBcdWFkZjhcdWI3OThcdWQ1MDRcdWM3NTggXHViNDUwIFx1YzgxNVx1YzgxMCBcdWMzMGQgaSwgaiAoMSAmbGU7IGkgJmx0OyBqICZsZTsgbikgXHViMjk0IGE8c3ViPmk8XC9zdWI+ICZndDsgYTxzdWI+ajxcL3N1Yj4gXHVjNzdjXHViNTRjIFx1YWMwNFx1YzEyMFx1YzczY1x1Yjg1YyBcdWM1ZjBcdWFjYjBcdWI0MThcdWM1YjQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YzVmMFx1YWNiMFx1YzEzMVx1Yzc0NCBcdWQzMTBcdWJjYzRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjLCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1YzczY1x1Yjg1YyBcdWQwZDBcdWMwYzlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPjFcdWJjODggXHVjODE1XHVjODEwXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBuXHViYzg4IFx1YzgxNVx1YzgxMFx1YWU0Y1x1YzljMCBcdWMyMWNcdWQ2OGNcdWQ1NWNcdWIyZTQuIFx1ZDYwNFx1YzdhYyBcdWNjOThcdWI5YWMgXHVjOTExXHVjNzc4IFx1YzgxNVx1YzgxMFx1Yzc0NCBpIFx1YmM4OCBcdWM4MTVcdWM4MTBcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLjxcL2xpPlxyXG5cdDxsaT5pXHViYzg4IFx1YzgxNVx1YzgxMFx1Yzc3NCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHVkMGQwXHVjMGM5XHViNDE4XHVjNWM4XHViMmU0XHViYTc0LCBcdWIxMThcdWM1YjRcdWFjMDRcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWIyZTRcdWJhNzQsIGlcdWJjODggXHVjODE1XHVjODEwXHVhY2ZjIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJhYThcdWI0ZTAgXHVjODE1XHVjODEwXHVjNzQ0IFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWQ2YzQsIFx1ZDBkMFx1YzBjOVx1ZDU1YyBcdWM4MTVcdWM4MTBcdWM3NDQgXHViYWE4XHVjNTQ0IFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWQ1NThcdWIwOTggXHViOWNjXHViNGUwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWNkNWNcdWM4ODVcdWM4MDFcdWM3M2NcdWI4NWMsIFx1YWQ2Y1x1ZDU1YyBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVjZDFkIFx1YWMxY1x1YzIxOFx1YzY0MCwgXHVhYzAxIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL2xpPlxyXG48XC9vbD5cclxuXHJcbjxwPlx1YzU0Y1x1YWNlMFx1YjlhY1x1Yzk5OFx1Yzc0NCBcdWM3N2RcdWM3NDAgXHViM2Q5XHVjNmIxXHVjNzc0XHViMjk0LCBcdWM3NzQgXHViYjM4XHVjODFjXHVhYzAwIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWM1ZjBcdWFjYjAgXHVjZWY0XHVkM2VjXHViMTBjXHVkMmI4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWMyNmNcdWM2YjQgXHViYjM4XHVjODFjXHVjNzg0XHVjNzQ0IFx1YzU0Y1x1YWM4YyBcdWI0MThcdWM1YzhcdWIyZTQuIFx1YjNkOVx1YzZiMVx1Yzc3NFx1YjI5NCBcdWM3YWNcdWQ2MDRcdWM3NzRcdWM1ZDBcdWFjOGMgJnJkcXVvO1x1Yzc3NFx1YWM3MCBcdWFlNGFcdWM3NzQgXHVjNmIwXHVjMTIwIFx1ZDBkMFx1YzBjOVx1YzczY1x1Yjg1YyBcdWQ0ODBcdWJhNzQgXHViM2ZjPyZyZHF1bzsgXHViNzdjXHVhY2UwIFx1YmIzY1x1YzVjOFx1YjJlNC4gXHVjN2FjXHVkNjA0XHVjNzc0XHViMjk0IFx1YzU0NFx1YmIzNCBcdWIzMDBcdWIyZjVcdWIzYzQgXHVkNTU4XHVjOWMwIFx1YzU0YVx1YzU1OFx1YjJlNC4gXHViMmY5XHVjMmUwXHVjNzQwIFx1YzViNFx1YjViYlx1YWM4YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWIyOTRcdWFjMDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgbiAoMSAmbGU7IG4gJmxlOyAxLCAwMDAsIDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NTBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIG5cdWFjMWNcdWM3NTggXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBcdWM4MTVcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMyMWNcdWM1ZjRcdWM3NTggXHVjNmQwXHVjMThjIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPiBcdWM3NDQgXHViNzNiXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDZjXHVkNTVjIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYlx1YmM4OFx1YzlmOFx1Yjg1YyBcdWM5ZDFcdWQ1NjlcdWM3NTggXHVkMDZjXHVhZTMwIHM8c3ViPmk8XC9zdWI+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YWNlMCwgXHVjNzc0XHVkNmM0IFx1YWRmOCBcdWM5ZDFcdWQ1NjlcdWM1ZDAgXHVjMThkXHVkNTVjIHM8c3ViPmk8XC9zdWI+XHVhYzFjXHVjNzU4IFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YzgxMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgXHVjNjI0XHViOTg0XHVjYzI4XHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWM5ZDFcdWQ1NjlcdWM3NDQgXHVjZDljXHViODI1XHVkNTYwIFx1YjU0YywgXHVjOWQxXHVkNTY5XHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NDQgXHVhZTMwXHVjOTAwXHVjNzNjXHViODVjIFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzYwOFx1YzgxY1x1Yzc1OCBcdWMyMWNcdWM1ZjQgXHVhZGY4XHViNzk4XHVkNTA0XHViOTdjIFx1YWRmOFx1YjlhY1x1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC9wcm9ibGVtXC83OTgyXC8yLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjQ0cHg7IHdpZHRoOjE0MHB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3OTgyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiSW52ZXJzaW9ucyIsImRlc2NyaXB0aW9uIjoiPHA+Qnl0ZWFzYXIgZGlzY292ZXJlZCBhIG5ldyBmYW1pbHkgb2YgdW5kaXJlY3RlZCBncmFwaHMgdGhhdCBjYW4gYmUgcmVwcmVzZW50ZWQgdXNpbmcgcGVybXV0YXRpb25zLiBMZXQgViA9IHsxLCAyLCAuLi4sIG59IGJlIHRoZSBzZXQgb2YgdmVydGljZXMuIFRoZSBkZXNjcmlwdGlvbiBvZiBhIGdyYXBoIGlzIGdpdmVuIGFzIGEgcGVybXV0YXRpb24gYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IG9mIHRoZSBzZXQgViAodGhhdCBpcywgYSBzZXF1ZW5jZSBvZiBkaXN0aW5jdCBudW1iZXJzIGZyb20gViApLiBUaGUgdmVydGljZXMgYWkgYW5kIGFqIGFyZSBjb25uZWN0ZWQgYnkgYW4gZWRnZSBpZiB0aGUgcGFpciAoaSwgaikgZm9ybXMgYW4gaW52ZXJzaW9uIGluIHRoZSBwZXJtdXRhdGlvbiwgdGhhdCBpcywgaSAmbHQ7IGogYW5kIGE8c3ViPmk8XC9zdWI+ICZndDsgYTxzdWI+ajxcL3N1Yj4gLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgbGV0IG4gPSA0IGFuZCBjb25zaWRlciB0aGUgcGVybXV0YXRpb24gMiwgMywgMSwgNC4gRnJvbSB0aGlzIHBlcm11dGF0aW9uIHdlIG9idGFpbiB0aGUgZm9sbG93aW5nIGdyYXBoOjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246Y2VudGVyXCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvNzk4MlwvMS5wbmdcIiBzdHlsZT1cImhlaWdodDo0NXB4OyB3aWR0aDoxNTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5CeXRlYXNhciB3b3VsZCBsaWtlIHRvIGNoZWNrIGlmIHRoZSByZXByZXNlbnRhdGlvbiB0aGF0IGhlIGludmVudGVkIGlzIHVzZWZ1bCBpbmRlZWQuIEhlIGhhcyBkZWNpZGVkIHRvIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIGFsbCB0aGUgY29ubmVjdGVkIGNvbXBvbmVudHMgb2YgdGhlIGdyYXBoLiBSZWNhbGwgdGhhdCB0d28gdmVydGljZXMgdTsgdiAmaXNpbjsgViBiZWxvbmcgdG8gdGhlIHNhbWUgY29ubmVjdGVkIGNvbXBvbmVudCBpZiB0aGVyZSBleGlzdHMgYSBzZXF1ZW5jZSBvZiB2ZXJ0aWNlcyBzdGFydGluZyB3aXRoIHUgYW5kIGVuZGluZyB3aXRoIHYgc3VjaCB0aGF0IGV2ZXJ5IHR3byBzdWJzZXF1ZW50IHZlcnRpY2VzIGluIHRoZSBzZXF1ZW5jZSBhcmUgY29ubmVjdGVkIGJ5IGFuIGVkZ2UuIEluIG91ciBleGFtcGxlIHdlIGhhdmUgdHdvIGNvbm5lY3RlZCBjb21wb25lbnRzOiB7MSwgMiwgM30gYW5kIHs0fS48XC9wPlxyXG5cclxuPHA+SGVscCBCeXRlYXNhciE8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4gKDEgJmxlOyBuICZsZTsgMSAwMDAgMDAwKSwgdGhlIG51bWJlciBvZiB2ZXJ0aWNlcyBvZiB0aGUgZ3JhcGguIFRoZSBzZWNvbmQgbGluZSBjb250YWlucyBuIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gdGhlIG51bWJlciBvZiBjb25uZWN0ZWQgY29tcG9uZW50cyBpbiB0aGUgZ3JhcGguIERlbm90ZSB0aGlzIG51bWJlciBieSBtLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgbSBsaW5lcyBzaG91bGQgaG9sZCBhIGRlc2NyaXB0aW9uIG9mIG9uZSBjb25uZWN0ZWQgY29tcG9uZW50LiBGaXJzdCBhIG51bWJlciBrIHNob3VsZCBiZSB3cml0dGVuOiB0aGUgc2l6ZSBvZiB0aGUgY29tcG9uZW50LiBUaGVuLCBhbiBpbmNyZWFzaW5nIHNlcXVlbmNlIG9mIGsgdmVydGV4IG51bWJlcnMgb2YgdGhlIGNvbXBvbmVudCBzaG91bGQgYmUgd3JpdHRlbi4gVGhlIGNvbXBvbmVudHMgc2hvdWxkIGJlIGxpc3RlZCBpbiBzdWNoIG9yZGVyIHRoYXQgdGhlIG51bWJlcnMgb2YgdGhlIGZpcnN0IG5vZGVzIG9mIHRoZSBjb21wb25lbnRzIGZvcm0gYW4gaW5jcmVhc2luZyBzZXF1ZW5jZS4gSW4gb3RoZXIgd29yZHMsIGlmIFMgYW5kIFMmcHJpbWU7IGFyZSB0d28gY29ubmVjdGVkIGNvbXBvbmVudHMsIHUgJmlzaW47IFMsIHYgJmlzaW47IFMmcHJpbWU7IGFyZSB0aGVpciBub2RlcyB3aXRoIHRoZSBzbWFsbGVzdCBudW1iZXIgYW5kIHUgJmx0OyB2LCB0aGVuIHRoZSBjb21wb25lbnQgUyBzaG91bGQgYmUgbGlzdGVkIGVhcmxpZXIgdGhhbiBTJnByaW1lOy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=