- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۱۲۸ مگابایت
- منبع: amppz 2012
اصغر پرنده در حال گشت زدن در جای خود بود که یک جایگشت \(n\) تایی پیدا کرد. جویای نام جایگشت شد و فهمید که نامش \(P\) است و عدد \(i\)ام آن هم \(P_{i}\) است. از آنجایی که اصغر یارانه میگیرد و از نظر اقتصادی تامین است، بیکار است و گرافی \(n\) راسی میسازد و بین رئوس \(i\) و \(j\) در گراف یال میگذارد اگر \((i-j) \times (P_{i}-P_{j})\) کمتر از صفر باشد و همچنین \(i\) و \(j\) برابر نباشند.
اصغر میخواهد مولفههای همبندی گرافی که ساخته است را بدست آورد. از آنجایی که اصغر آنقدر هم بیکار نیست و ادمین یکی از چنلهای تلگرام است از شما میخواهد این کار را برایش انجام دهید.
ورودی
در خط اول ورودی عدد \(n\) آمده است.
در خط دوم، \(n\) عدد که \(i\)امین عدد نشان دهنده عضو \(i\)ام جایگشت (یعنی \(P_{i}\)) است. میدانیم که در جایگشت تمام اعداد از ۱ تا \(n\) و متفاوت اند.
\[1 \le n \le 1\ 000\ 000\]
خروجی
در خط اول ورودی تعداد مولفههای همبندی گراف را چاپ کنید. در خطوط بعدی، در هر خط باید رئوس یک مولفه را چاپ کنید. عدد اول هر خط نشان دهنده تعداد رئوس مولفه و اعداد بعدی شماره رئوس درون این مولفه اند.
رئوس هر مولفه را بر حسب شماره رأس از کوچکترین به بزرگترین چاپ کنید. مولفهها را به ترتیب کوچکترین رأسشان از کوچکترین به بزرگترین چاپ کنید.
توجه کنید که خروجی یکتاست!
نمره دهی
نمره دهی این سوال به این صورت است که اگر شما \(x\) درصد از تستها را درست جواب بدهید نمره شما \(x\) خواهد شد.
در ۱/۳ تستها \(n\) کمتر از ۱۰۰۰ است.
مثال
ورودی نمونه
4
2 3 1 4
خروجی نمونه
2
3 1 2 3
1 4
گراف دو یال دارد که رئوس (۱,۳) و (۲,۳) را به هم وصل میکنند.