시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 182 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/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWMyMWNcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0IG4gKDEgJmxlOyBuICZsZTsgMSwgMDAwLCAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgblx1YWMxY1x1Yzc1OCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDFjIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzIxY1x1YzVmNFx1Yzc1OCBcdWM2ZDBcdWMxOGMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IFx1Yzc0NCBcdWI3M2JcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhZDZjXHVkNTVjIFx1YzlkMVx1ZDU2OVx1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDZjNCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzlkMVx1ZDU2OVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Y2NhYiBcdWJjODhcdWM5ZjhcdWI4NWMgXHVjOWQxXHVkNTY5XHVjNzU4IFx1ZDA2Y1x1YWUzMCBzPHN1Yj5pPFwvc3ViPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWFjZTAsIFx1Yzc3NFx1ZDZjNCBcdWFkZjggXHVjOWQxXHVkNTY5XHVjNWQwIFx1YzE4ZFx1ZDU1YyBzPHN1Yj5pPFwvc3ViPlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IFx1YzYyNFx1Yjk4NFx1Y2MyOFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2MCBcdWI1NGMsIFx1YzlkMVx1ZDU2OVx1YzVkMCBcdWMxOGRcdWQ1NWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWJjODhcdWQ2MzhcdWM3NTggXHVjODE1XHVjODEwXHVjNzQ0IFx1YWUzMFx1YzkwMFx1YzczY1x1Yjg1YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2MDhcdWM4MWNcdWM3NTggXHVjMjFjXHVjNWY0IFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yjk3YyBcdWFkZjhcdWI5YWNcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMtYXAtbm9ydGhlYXN0LTEuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvNzk4MlwvMi5wbmdcIiBzdHlsZT1cImhlaWdodDo0NHB4OyB3aWR0aDoxNDBweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNzk4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkludmVyc2lvbnMiLCJkZXNjcmlwdGlvbiI6IjxwPkJ5dGVhc2FyIGRpc2NvdmVyZWQgYSBuZXcgZmFtaWx5IG9mIHVuZGlyZWN0ZWQgZ3JhcGhzIHRoYXQgY2FuIGJlIHJlcHJlc2VudGVkIHVzaW5nIHBlcm11dGF0aW9ucy4gTGV0IFYgPSB7MSwgMiwgLi4uLCBufSBiZSB0aGUgc2V0IG9mIHZlcnRpY2VzLiBUaGUgZGVzY3JpcHRpb24gb2YgYSBncmFwaCBpcyBnaXZlbiBhcyBhIHBlcm11dGF0aW9uIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPiBvZiB0aGUgc2V0IFYgKHRoYXQgaXMsIGEgc2VxdWVuY2Ugb2YgZGlzdGluY3QgbnVtYmVycyBmcm9tIFYgKS4gVGhlIHZlcnRpY2VzIGFpIGFuZCBhaiBhcmUgY29ubmVjdGVkIGJ5IGFuIGVkZ2UgaWYgdGhlIHBhaXIgKGksIGopIGZvcm1zIGFuIGludmVyc2lvbiBpbiB0aGUgcGVybXV0YXRpb24sIHRoYXQgaXMsIGkgJmx0OyBqIGFuZCBhPHN1Yj5pPFwvc3ViPiAmZ3Q7IGE8c3ViPmo8XC9zdWI+IC48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCBuID0gNCBhbmQgY29uc2lkZXIgdGhlIHBlcm11dGF0aW9uIDIsIDMsIDEsIDQuIEZyb20gdGhpcyBwZXJtdXRhdGlvbiB3ZSBvYnRhaW4gdGhlIGZvbGxvd2luZyBncmFwaDo8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOmNlbnRlclwiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLWFwLW5vcnRoZWFzdC0xLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzc5ODJcLzEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NDVweDsgd2lkdGg6MTUzcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+Qnl0ZWFzYXIgd291bGQgbGlrZSB0byBjaGVjayBpZiB0aGUgcmVwcmVzZW50YXRpb24gdGhhdCBoZSBpbnZlbnRlZCBpcyB1c2VmdWwgaW5kZWVkLiBIZSBoYXMgZGVjaWRlZCB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyBhbGwgdGhlIGNvbm5lY3RlZCBjb21wb25lbnRzIG9mIHRoZSBncmFwaC4gUmVjYWxsIHRoYXQgdHdvIHZlcnRpY2VzIHU7IHYgJmlzaW47IFYgYmVsb25nIHRvIHRoZSBzYW1lIGNvbm5lY3RlZCBjb21wb25lbnQgaWYgdGhlcmUgZXhpc3RzIGEgc2VxdWVuY2Ugb2YgdmVydGljZXMgc3RhcnRpbmcgd2l0aCB1IGFuZCBlbmRpbmcgd2l0aCB2IHN1Y2ggdGhhdCBldmVyeSB0d28gc3Vic2VxdWVudCB2ZXJ0aWNlcyBpbiB0aGUgc2VxdWVuY2UgYXJlIGNvbm5lY3RlZCBieSBhbiBlZGdlLiBJbiBvdXIgZXhhbXBsZSB3ZSBoYXZlIHR3byBjb25uZWN0ZWQgY29tcG9uZW50czogezEsIDIsIDN9IGFuZCB7NH0uPFwvcD5cclxuXHJcbjxwPkhlbHAgQnl0ZWFzYXIhPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBuICgxICZsZTsgbiAmbGU7IDEgMDAwIDAwMCksIHRoZSBudW1iZXIgb2YgdmVydGljZXMgb2YgdGhlIGdyYXBoLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgbiBpbnRlZ2VycyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj4uPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHRoZSBudW1iZXIgb2YgY29ubmVjdGVkIGNvbXBvbmVudHMgaW4gdGhlIGdyYXBoLiBEZW5vdGUgdGhpcyBudW1iZXIgYnkgbS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIG0gbGluZXMgc2hvdWxkIGhvbGQgYSBkZXNjcmlwdGlvbiBvZiBvbmUgY29ubmVjdGVkIGNvbXBvbmVudC4gRmlyc3QgYSBudW1iZXIgayBzaG91bGQgYmUgd3JpdHRlbjogdGhlIHNpemUgb2YgdGhlIGNvbXBvbmVudC4gVGhlbiwgYW4gaW5jcmVhc2luZyBzZXF1ZW5jZSBvZiBrIHZlcnRleCBudW1iZXJzIG9mIHRoZSBjb21wb25lbnQgc2hvdWxkIGJlIHdyaXR0ZW4uIFRoZSBjb21wb25lbnRzIHNob3VsZCBiZSBsaXN0ZWQgaW4gc3VjaCBvcmRlciB0aGF0IHRoZSBudW1iZXJzIG9mIHRoZSBmaXJzdCBub2RlcyBvZiB0aGUgY29tcG9uZW50cyBmb3JtIGFuIGluY3JlYXNpbmcgc2VxdWVuY2UuIEluIG90aGVyIHdvcmRzLCBpZiBTIGFuZCBTJnByaW1lOyBhcmUgdHdvIGNvbm5lY3RlZCBjb21wb25lbnRzLCB1ICZpc2luOyBTLCB2ICZpc2luOyBTJnByaW1lOyBhcmUgdGhlaXIgbm9kZXMgd2l0aCB0aGUgc21hbGxlc3QgbnVtYmVyIGFuZCB1ICZsdDsgdiwgdGhlbiB0aGUgY29tcG9uZW50IFMgc2hvdWxkIGJlIGxpc3RlZCBlYXJsaWVyIHRoYW4gUyZwcmltZTsuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d