You are given a sequence a_1, a_2, ..., a_{n} consisting of different integers. It is required to split this sequence into the maximum number of subsequences such that after sorting integers in each of them in increasing order, the total sequence also will be sorted in increasing order.

Sorting integers in a subsequence is a process such that the numbers included in a subsequence are ordered in increasing order, and the numbers which are not included in a subsequence don't change their places.

Every element of the sequence must appear in exactly one subsequence.


-----Input-----

The first line of input data contains integer n (1 ≤ n ≤ 10^5) — the length of the sequence.

The second line of input data contains n different integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9) — the elements of the sequence. It is guaranteed that all elements of the sequence are distinct.


-----Output-----

In the first line print the maximum number of subsequences k, which the original sequence can be split into while fulfilling the requirements.

In the next k lines print the description of subsequences in the following format: the number of elements in subsequence c_{i} (0 < c_{i} ≤ n), then c_{i} integers l_1, l_2, ..., l_{c}_{i} (1 ≤ l_{j} ≤ n) — indices of these elements in the original sequence. 

Indices could be printed in any order. Every index from 1 to n must appear in output exactly once.

If there are several possible answers, print any of them.


-----Examples-----
Input
6
3 2 1 6 5 4

Output
4
2 1 3
1 2
2 4 6
1 5

Input
6
83 -75 -49 11 37 62

Output
1
6 1 2 3 4 5 6



-----Note-----

In the first sample output:

After sorting the first subsequence we will get sequence 1 2 3 6 5 4.

Sorting the second subsequence changes nothing.

After sorting the third subsequence we will get sequence 1 2 3 4 5 6.

Sorting the last subsequence changes nothing.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph traversal

Sorting

Implementation

Mathematics

Spanning trees


Solutions:
from sys import stdin, stdout

def find(node):
	x = []
	while dsu[node] > 0:
		x.append(node)
		node = dsu[node]
	for i in x:
		dsu[i] = node
	return node

def union(node1, node2):
	if node1 != node2:
		if dsu[node1] > dsu[node2]:
			(node1, node2) = (node2, node1)
		dsu[node1] += dsu[node2]
		dsu[node2] = node1
n = int(stdin.readline().strip())
arr = [(int(j), i) for (i, j) in enumerate(stdin.readline().strip().split())]
arr = sorted(arr, key=lambda t: t[0], reverse=False)
dsu = [-1] * (n + 1)
for i in range(n):
	p_a = find(arr[i][1] + 1)
	p_b = find(i + 1)
	union(p_a, p_b)
k = 0
outputs = [[] for __ in range(n + 1)]
for i in range(1, n + 1):
	if dsu[i] < 0:
		k += 1
	outputs[find(i)].append(f'{i}')
stdout.write(f'{k}\n')
for output in outputs:
	if output:
		stdout.write(f'{len(output)} ')
		stdout.write(' '.join(output) + '\n')


n = int(input())
a = sorted(zip(map(int, input().split()), range(n)))
s = []
for i in range(n):
	if a[i]:
		s.append([])
		j = i
		while a[j]:
			s[-1].append(j + 1)
			(a[j], j) = (None, a[j][1])
print(len(s))
for l in s:
	print(len(l), *l)


import sys
n = int(input())
a = list(map(int, input().split()))
a = sorted([(a[i], i) for i in range(n)])
d = []
c = [False] * n
for i in range(n):
	if not c[i]:
		k = i
		p = []
		while not c[k]:
			c[k] = True
			p.append(str(k + 1))
			k = a[k][1]
		d.append(p)
print(len(d))
for i in d:
	print(str(len(i)) + ' ' + ' '.join(i))


from sys import stdin
n = int(stdin.readline().strip())
a = list(map(int, stdin.readline().strip().split()))
a = [(a[i], i + 1) for i in range(n)]
a.sort()
used = [False] * (n + 1)
ss = []
for i in range(1, n + 1):
	if not used[i]:
		s = [i]
		used[i] = True
		j = i
		while True:
			j = a[j - 1][1]
			if not used[j]:
				s.append(j)
				used[j] = True
			else:
				break
		ss.append(s)
print(len(ss))
for s in ss:
	print(len(s), ' '.join(list(map(str, s))))


import math
import collections
import bisect
import heapq
import time
import random
import itertools
N = int(input())
A = [int(x) for x in input().split()]
B = [x for x in A]
B.sort()
ind = {v: i for (i, v) in enumerate(B)}
order = [ind[A[i]] for i in range(N)]
done = [0] * N
ans = []
for i in range(N):
	if not done[i]:
		g = []
		cur = i
		while not done[cur]:
			g.append(cur)
			done[cur] = 1
			cur = order[cur]
		ans.append([len(g)] + [j + 1 for j in g])
print(len(ans))
for row in ans:
	print(' '.join(map(str, row)))


from sys import stdin
n = int(stdin.readline().rstrip())
data = list(map(int, stdin.readline().rstrip().split()))
dic = {}
for (idx, val) in enumerate(data):
	dic[val] = idx + 1
dd = {}
data.sort()
nData = [0]
count = 1
for val in data:
	dd[count] = dic[val]
	count += 1
data = [0] * (n + 1)
for key in dd:
	data[dd[key]] = key
rs = []
mark = [False] * (n + 1)
for i in range(1, n + 1):
	val = i
	itrt = []
	if mark[i]:
		continue
	while True:
		itrt.append(val)
		mark[val] = True
		val = data[val]
		if val == i:
			break
	rs.append(itrt)
print(len(rs))
for ll in rs:
	print('{0} {1}'.format(len(ll), ' '.join(list(map(str, ll)))))


n = int(input())
a = [int(i) for i in input().split()]
a = [i[0] for i in sorted(enumerate(a), key=lambda x: x[1])]
checker = [0 for i in range(n)]
ans_set = []
for i in range(n):
	if checker[i] == 0:
		tmp = set([i])
		next_step = i
		next_step = a[next_step]
		while next_step != i:
			checker[next_step] = 1
			tmp.add(next_step)
			next_step = a[next_step]
		ans_set.append(tmp)
print(len(ans_set))
for tmp in ans_set:
	print(len(tmp), end=' ')
	for j in tmp:
		print(j + 1, end=' ')
	print()


n = int(input())
a = list(map(int, input().split()))
sorted_a = sorted(a)
d = {}
for i in range(len(a)):
	d[sorted_a[i]] = i
for i in range(len(a)):
	a[i] = d[a[i]]
res = []
done = [False] * n
for i in a:
	if done[i]:
		continue
	done[i] = True
	curr_subseq = set([i])
	next_item = a[i]
	while next_item not in curr_subseq:
		curr_subseq.add(next_item)
		done[next_item] = True
		next_item = a[next_item]
	res.append(curr_subseq)
print(len(res))
for i in res:
	curr = [str(j + 1) for j in list(i)]
	print(len(curr), end=' ')
	print(' '.join(curr))


import sys
input = sys.stdin.readline
from bisect import bisect_left as bs

def solve(n, a):
	b = a[:]
	b.sort()
	done = [0] * n
	res = []
	for i in range(n):
		if not done[i]:
			if a[i] == b[i]:
				res.append([i + 1])
				done[i] = 1
			else:
				r = []
				while not done[i]:
					r.append(i + 1)
					done[i] = 1
					i = bs(b, a[i])
				res.append(r)
	return res
n = int(input())
a = list(map(int, input().split()))
res = solve(n, a)
print(len(res))
for r in res:
	print(len(r), *r)


n = int(input())
a = list(map(int, input().split()))
b = a.copy()
b.sort()
pos = {x: i for (i, x) in enumerate(b)}
vis = [False] * n
subs = []
for x in a:
	if vis[pos[x]]:
		continue
	I = []
	while not vis[pos[x]]:
		I.append(pos[x] + 1)
		vis[pos[x]] = True
		x = a[pos[x]]
	subs.append(I)
print(len(subs))
for I in subs:
	print(len(I), *I)


import sys
input = sys.stdin.readline
from collections import defaultdict

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
n = int(input())
a = list(map(int, input().split()))
b = a[:]
b.sort()
d = defaultdict(int)
for i in range(n):
	d[b[i]] = i
uf = Unionfind(n)
for i in range(n):
	uf.unite(i, d[a[i]])
ans = defaultdict(list)
for i in range(n):
	ans[uf.root(i)].append(i)
print(len(list(ans.keys())))
for l in ans.values():
	print(len(l), *list(map(lambda x: x + 1, l)))


from sys import stdin
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
n = I()
v = [1] * n
a = list(R())
d = {}
for (i, j) in enumerate(sorted(a)):
	d[j] = i
for i in range(n):
	a[i] = d[a[i]]
ans = []
for i in a:
	if v[i]:
		ans += ([],)
		while v[i]:
			ans[-1] += (i + 1,)
			v[i] = 0
			i = a[i]
print(len(ans))
for i in ans:
	print(len(i), *i)


n = int(input())
a = list(map(int, input().split()))
a = [(a[i], i + 1) for i in range(n)]
a.sort()
seen = [0] * (n + 1)
ss = []
for i in range(1, n + 1):
	if seen[i] == 0:
		s = [i]
		seen[i] = 1
		j = i
		while True:
			j = a[j - 1][1]
			if seen[j] == 0:
				s.append(j)
				seen[j] = 1
			else:
				break
		ss.append(s)
print(len(ss))
for i in ss:
	print(len(i), ' '.join(list(map(str, i))))


from sys import stdin, stdout

def rint():
	return map(int, stdin.readline().split())
n = int(input())
seqin = list(rint())
seq = []
for i in range(n):
	seq.append((seqin[i], i))
seq.sort()
subseqs = []
done = [0 for i in range(n)]
for i in range(n):
	s = i
	if done[s]:
		continue
	else:
		subseq = []
	while done[s] != 1:
		done[s] = 1
		subseq.append(s + 1)
		s = seq[s][1]
	subseqs.append(subseq)
print(len(subseqs))
for subseq in subseqs:
	print(len(subseq), *subseq)


n = int(input())
anss = 0
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append([i, a[i], 0])
b = sorted(b, key=lambda a: a[1])
for i in range(n):
	b[i].append(i)
b = sorted(b, key=lambda a: a[0])
for i in range(n):
	if b[i][2] != 1:
		j = i
		anss = anss + 1
		while b[j][2] != 1:
			b[j][2] = b[j][2] + 1
			j = b[j][3]
print(anss)
for i in range(n):
	if b[i][2] != 2:
		c = []
		ans = 0
		j = i
		p = []
		while b[j][2] != 2:
			b[j][2] = b[j][2] + 1
			p.append(str(j + 1))
			ans = ans + 1
			j = b[j][3]
		print(str(len(p)) + ' ' + ' '.join(p))


n = int(input())
a = list(map(int, input().split()))
ans = sorted(a)
ind = {a[i]: i for i in range(n)}
done = [False] * n
total = 0
total_moves = []
for i in range(n):
	if done[i] == False:
		start = a[i]
		done[i] = True
		moves = []
		moves.append(i + 1)
		end = ans[i]
		while start != end:
			moves.append(ind[end] + 1)
			done[ind[end]] = True
			end = ans[ind[end]]
		total_moves.append(moves)
print(len(total_moves))
for i in total_moves:
	print(len(i), end=' ')
	for j in i:
		print(j, end=' ')
	print()


n = int(input())
a = list(map(int, input().split()))
a = sorted(range(n), key=lambda i: a[i])
s = []
for i in range(n):
	if a[i] + 1:
		l = []
		s.append(l)
		while a[i] + 1:
			l.append(i + 1)
			(a[i], i) = (-1, a[i])
print(len(s))
for l in s:
	print(len(l), *l)


n = int(input())
a = input().split()
a = [(int(a[i]), i) for i in range(n)]
a.sort()
start = 0
used = set()
b = []
while start < n:
	t = []
	cur = start
	first = True
	while cur != start or first:
		first = False
		t.append(cur + 1)
		used.add(cur)
		cur = a[cur][1]
	b.append(t)
	while start in used:
		start += 1
print(len(b))
for t in b:
	print(len(t), end=' ')
	print(*t)


from __future__ import print_function
import sys
sys.setrecursionlimit(100005)
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
pos = {}
for i in range(n):
	pos[b[i]] = i
g = [[] for _ in range(n)]
used = [False for _ in range(n)]
for i in range(n):
	g[i] += [pos[a[i]]]
b = []
for i in range(n):
	if used[i] == False:
		w = []
		q = [i]
		while q:
			v = q[-1]
			q.pop()
			w.append(v)
			used[v] = True
			for to in g[v]:
				if used[to] == False:
					q += [to]
		b.append(list(w))
print(len(b))
for i in range(len(b)):
	b[i] = [x + 1 for x in b[i]]
	print(len(b[i]), *b[i], sep=' ')


n = int(input())
a = [int(x) for x in input().split()]
a = list(enumerate(a))
a = sorted(a, key=lambda x: x[1])
a = [(i, x, j) for (j, (i, x)) in enumerate(a)]
a = sorted(a, key=lambda x: x[0])
count_cycles = 0
cycle = [-1] * n
i = 0
while True:
	while i < n and cycle[i] >= 0:
		i += 1
	if i == n:
		break
	k = i
	cycle[i] = count_cycles
	while a[k][2] != i:
		k = a[k][2]
		cycle[k] = count_cycles
	count_cycles += 1
print(count_cycles)
cycles = [[] for i in range(count_cycles)]
for i in range(n):
	cycles[cycle[i]].append(i + 1)
for i in range(count_cycles):
	print(str(len(cycles[i])) + ' ' + ' '.join([str(x) for x in cycles[i]]))


import sys
input = sys.stdin.readline
n = int(input())
b = list(map(int, input().split()))
bb = sorted(b)
c = {bb[i]: i for i in range(n)}
a = [c[b[i]] for i in range(n)]
vis = [0] * n
out = []
for i in range(n):
	if vis[i]:
		continue
	vis[i] = 1
	newlist = [i]
	while a[newlist[-1]] != i:
		newlist.append(a[newlist[-1]])
		vis[newlist[-1]] = 1
	out.append(newlist)
print(len(out))
for i in out:
	print(' '.join(map(lambda x: str(x + 1), [len(i) - 1] + i)))


n = int(input())
a = list(map(int, input().split()))
sa = sorted(a)
sg = {}
for i in range(n):
	sg[sa[i]] = i
vis = set()
ans = []
for i in range(n):
	if i in vis:
		continue
	vis.add(i)
	c = [i + 1]
	v = i
	while 1:
		nv = sg[a[v]]
		if nv not in vis:
			vis.add(nv)
			c.append(nv + 1)
			v = nv
		else:
			break
	ans.append(c)
print(len(ans))
for c in ans:
	print(len(c), ' '.join([str(e) for e in c]))


def binSearch(arr, el):
	if len(arr) == 0:
		return -1
	(l, p) = (0, len(arr) - 1)
	while l != p:
		s = (l + p) // 2
		if arr[s] < el:
			l = s + 1
		else:
			p = s
	return l if arr[l] == el else -1
n = int(input())
a = [int(i) for i in input().split()]
s = sorted(a)
subsList = []
visited = [False for i in range(n)]
for i in range(n):
	ind = i
	newSub = False
	while not visited[ind]:
		if not newSub:
			subsList.append([])
		newSub = True
		visited[ind] = True
		subsList[-1].append(str(ind + 1))
		ind = binSearch(s, a[ind])
out = str(len(subsList)) + '\n'
for lineNr in range(len(subsList) - 1):
	out += str(len(subsList[lineNr])) + ' '
	out += ' '.join(subsList[lineNr]) + '\n'
out += str(len(subsList[-1])) + ' '
out += ' '.join(subsList[-1])
print(out)


n = int(input())
m = list(map(int, input().split()))
d = {}
for (i, k) in enumerate(sorted(m)):
	d[k] = i
r = set()
ans = []
for (i, k) in enumerate(m, start=1):
	if k not in r:
		r.add(k)
		ans.append({i})
		j = k
		while m[d[j]] != k:
			r.add(m[d[j]])
			ans[-1].add(d[j] + 1)
			j = m[d[j]]
print(len(ans))
for s in ans:
	print(len(s), *s)


from sys import stdin, stdout
n = int(stdin.readline().rstrip())
a = [int(x) for x in stdin.readline().rstrip().split()]
sorted_position = {}
sortat = sorted(a)
for i in range(n):
	sorted_position[sortat[i]] = i
all_set = set()
result = []
for i in range(n):
	crt_set = []
	if i not in all_set:
		crt_set.append(i)
		all_set.add(i)
		next_pos = sorted_position[a[i]]
		next_elem = a[next_pos]
		while next_pos not in all_set:
			crt_set.append(next_pos)
			all_set.add(next_pos)
			next_pos = sorted_position[next_elem]
			next_elem = a[next_pos]
		result.append(crt_set)
print(len(result))
for s in result:
	print(len(s), end=' ')
	for e in s:
		print(e + 1, end=' ')
	print()


from collections import defaultdict

def DFS(d, visited, x):
	stack = [x]
	ans = []
	while len(stack):
		temp = stack.pop()
		visited[temp] = 1
		ans.append(temp + 1)
		for i in d[temp]:
			if visited[i] == 0:
				stack.append(i)
				visited[temp] = 1
	return ans
n = int(input())
l = list(map(int, input().split()))
act_pos = {l[i]: i for i in range(n)}
pos = []
t = sorted(l)
pos = {t[i]: i for i in range(n)}
d = defaultdict(list)
for i in l:
	d[act_pos[i]].append(pos[i])
visited = [0 for i in range(n)]
ans = []
for i in range(n):
	if visited[i] == 0:
		k = list(DFS(d, visited, i))
		t1 = k[::-1]
		t1.append(len(k))
		ans.append(t1[::-1])
print(len(ans))
for i in ans:
	print(*i)


n = int(input())
a = list(map(int, input().split()))
x = sorted([(a[i], i) for i in range(n)])
cycles = []
was = [False for i in range(n)]
for i in range(n):
	if was[i]:
		continue
	cur = i
	cyc = []
	while not was[cur]:
		was[cur] = True
		cyc.append(cur + 1)
		cur = x[cur][1]
	cycles.append(cyc)
print(len(cycles))
for cyc in cycles:
	print(len(cyc), ' '.join(map(str, cyc)))


from sys import stdin
from collections import defaultdict

def dfs(graph, seen, start):
	if seen[start]:
		return None
	visit = [start]
	ans = []
	while visit:
		node = visit.pop()
		seen[node] = True
		ans.append(node)
		for v in graph[node]:
			if not seen[v]:
				visit.append(v)
	return ans

def main(n, arr):
	orig = {}
	for i in range(n):
		val = arr[i]
		orig[val] = i
	_arr = sorted(arr)
	g = defaultdict(list)
	for i in range(n):
		val = _arr[i]
		origpos = orig[val]
		g[origpos].append(i)
	seen = [False] * n
	ans = []
	for i in range(n):
		if not seen[i]:
			ans.append(dfs(g, seen, i))
	print(len(ans))
	for a in ans:
		print(len(a), ' '.join(map(lambda x: str(x + 1), a)))

def __starting_point():
	n = int(stdin.readline())
	arr = list(map(int, stdin.readline().split(' ')))
	main(n, arr)
__starting_point()


n = int(input())
lis = list(map(int, input().split()))
a = sorted(lis)[:]
d = {}
for i in range(n):
	d[a[i]] = i
vis = [0] * n
ans = []
for i in range(n):
	tmp = []
	if vis[i] == 0:
		j = i
		while vis[j] == 0:
			vis[j] = 1
			tmp.append(j + 1)
			j = d[lis[j]]
		ans.append([len(tmp)] + tmp)
print(len(ans))
for i in ans:
	print(*i)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
n = ii()
l = il()
l2 = sorted(l)
sd = dict(((l2[i], i) for i in range(n)))
ans = []
lvis = set()
for i in range(n):
	if not l[i] in lvis:
		tmp = [i + 1]
		x = sd[l[i]]
		lvis.add(l[i])
		while x != i:
			lvis.add(l[x])
			tmp.append(x + 1)
			x = sd[l[x]]
		ans.append(tmp)
print(len(ans))
for i in ans:
	print(len(i), *i)


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

class DSU:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.rank = [0 for i in range(n + 1)]

	def find_set(self, v):
		if v == self.parent[v]:
			return v
		self.parent[v] = self.find_set(self.parent[v])
		return self.parent[v]

	def union(self, a, b):
		a = self.find_set(a)
		b = self.find_set(b)
		if a != b:
			if self.rank[a] < self.rank[b]:
				(a, b) = (b, a)
			self.parent[b] = a
			if self.rank[a] == self.rank[b]:
				self.rank[a] += 1

def main():
	try:
		n = I()
		l = list(enumerate(list(In()), start=1))
		l.sort(key=lambda x: x[1])
		dsu = DSU(n)
		for i in range(n):
			dsu.union(i + 1, l[i][0])
		d = defaultdict(list)
		for i in range(1, n + 1):
			d[dsu.find_set(i)].append(i)
		print(len(d))
		for x in d:
			print(len(d[x]), *d[x])
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


n = int(input())
a = list(map(int, input().split()))
s = [(a[i], i) for i in range(n)]
s.sort()
x = [-1] * n
for i in range(n):
	x[s[i][1]] = i
ans = []
for i in range(n):
	if x[i] != -1:
		j = i
		q = []
		while x[j] != -1:
			q.append(str(j + 1))
			t = j
			j = x[j]
			x[t] = -1
		ans.append(str(len(q)) + ' ' + ' '.join(q))
print(len(ans))
print(*ans, sep='\n')


n = int(input())
a = list(map(int, input().split()))
ind = sorted(range(n), key=lambda i: a[i])
v = [False] * n
s = []
for i in range(n):
	if not v[i]:
		l = []
		s.append(l)
		while not v[i]:
			v[i] = True
			l.append(i + 1)
			i = ind[i]
print(len(s))
for l in s:
	print(len(l), *l)


n = int(input())
s = list(map(int, input().split()))
s1 = sorted(s)
d = {s1[i]: i for i in range(n)}
ans = []
for i in range(n):
	if d[s[i]] > -1:
		curans = [i + 1]
		cur = i
		place = d[s[cur]]
		while place != i:
			curans.append(place + 1)
			d[s[cur]] = -1
			cur = place
			place = d[s[cur]]
		d[s[cur]] = -1
		ans.append(curans)
print(len(ans))
for a in ans:
	print(len(a), end=' ')
	print(*a)


n = int(input())
l = list(map(int, input().split()))
x = sorted(l)
dm = {}
dc = {}
ans = []
for i in range(n):
	dm[x[i]] = i
	dc[i] = 0
for i in range(n):
	l[i] = dm[l[i]]
k = 0
for m in range(n):
	if dc[l[m]] == 1:
		continue
	dc[m] = 1
	k += 1
	temp = l[m]
	temp2 = [m]
	while m != temp:
		dc[temp] = 1
		temp2.append(temp)
		temp = l[temp]
	ans.append(temp2)
print(k)
for i in ans:
	print(len(i), end=' ')
	for j in i:
		print(j + 1, end=' ')
	print()


n = int(input())
a = list(map(int, input().split()))
a = sorted([(a[i], i) for i in range(n)])
b = []
c = [True] * n
for i in range(n):
	if c[i]:
		j = i
		d = []
		while c[j]:
			c[j] = False
			d.append(j + 1)
			j = a[j][1]
		b.append(d)
print(len(b))
for i in b:
	print(len(i), *i)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append([a[i], i])
b.sort()
destinations = [0] * n
inverses = [0] * n
for i in range(n):
	y = b[i][1]
	destinations[i] = y
	inverses[y] = i
visited = [0] * n
k = []
for i in range(n):
	if visited[i]:
		continue
	visited[i] = 1
	k.append([])
	k[-1].append(i)
	curr = destinations[i]
	while visited[curr] == 0:
		visited[curr] = 1
		k[-1].append(curr)
		curr = destinations[curr]
	curr = inverses[i]
	while visited[curr] == 0:
		visited[curr] = 1
		k[-1].append(curr)
		curr = inverses[curr]
ans = []
ans.append(str(len(k)))
for r in k:
	ans.append(str(len(r)))
	for j in r:
		ans.append(str(j + 1))
print(' '.join(ans))


from bisect import bisect
n = int(input().strip())
nums = [int(x) for x in input().strip().split()]
snums = sorted(nums)
checks = [False for _ in nums]
subsubs = []
for (i, n) in enumerate(nums):
	subs = []
	if checks[i]:
		continue
	checks[i] = True
	idx = i
	subs.append(idx + 1)
	while True:
		idx = bisect(snums, nums[idx]) - 1
		if checks[idx]:
			break
		else:
			checks[idx] = True
			subs.append(idx + 1)
	subsubs.append(subs)
print(len(subsubs))
for s in subsubs:
	print(len(s), end='')
	for item in s:
		print('', item, end='')
	print()


n = int(input())
d = list(map(int, input().split()))
temp = d[:]
d.sort()
from bisect import bisect_left
A = [bisect_left(d, i) for i in temp]
del d, temp
f = [False] * len(A)
result = []
for i in range(n):
	if not f[i]:
		L = [i + 1]
		f[i] = True
		j = A[i]
		while j != i:
			L.append(j + 1)
			f[j] = True
			j = A[j]
		result.append(L)
print(len(result))
for L in result:
	print(len(L), ' '.join(map(str, L)))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
n = int(input())
arr = list(map(int, input().split()))
d = {}
for i in range(n):
	d[arr[i]] = i
ans = []
ls = sorted(arr)
v = [0] * n
for i in range(n):
	pos = d[ls[i]]
	varr = []
	if v[pos] == 0:
		while v[pos] == 0:
			v[pos] = 1
			varr.append(pos + 1)
			pos = d[ls[pos]]
		ans.append(varr)
print(len(ans))
for i in ans:
	print(len(i), end=' ')
	print(*i)


n = int(input())
anss = 0
a = list(map(int, input().split()))
b = []
for i in range(n):
	b.append([i, a[i]])
b = sorted(b, key=lambda a: a[1])
c = []
d = []
e = [0] * n
for i in range(n):
	if e[i] != 1:
		j = i
		d.append(0)
		p = []
		while e[j] != 1:
			d[anss] = d[anss] + 1
			e[j] = 1
			p.append(str(j + 1))
			j = b[j][0]
		c.append(p)
		anss = anss + 1
print(anss)
for i in c:
	print(str(len(i)) + ' ' + ' '.join(i))


import sys
cases = int(sys.stdin.readline())
input_arr = [int(x) for x in sys.stdin.readline().strip().split(' ')]
sort = sorted(input_arr)
sorted_dict = dict()
for i in range(0, len(sort)):
	sorted_dict[sort[i]] = i + 1
array = []
for x in input_arr:
	array.append(sorted_dict[x])
seen = set()
my_dict = dict()
for i in range(1, len(array) + 1):
	my_dict[i] = array[i - 1]

def find_permutation(seen, x):
	permutation = []
	while x not in seen:
		permutation.append(x)
		seen.add(x)
		x = my_dict[x]
	return str(len(permutation)) + ' ' + ' '.join((str(x) for x in sorted(permutation)))
num_perms = 0
to_print = []
for x in array:
	if x not in seen:
		num_perms += 1
		to_print.append(find_permutation(seen, x))
		seen.add(x)
print(num_perms)
print('\n'.join(to_print))


import operator as op
input()
a = list((x[0] for x in sorted(enumerate(map(int, input().split())), key=op.itemgetter(1))))
ans = []
for i in range(len(a)):
	if a[i] != -1:
		j = a[i]
		a[i] = -1
		t = [i + 1]
		while j != i:
			t.append(j + 1)
			last = j
			j = a[j]
			a[last] = -1
		ans.append(t)
print(len(ans))
for i in range(len(ans)):
	print(len(ans[i]), *ans[i])


n = int(input())
a = list(map(int, input().split()))
x = sorted([(a[i], i) for i in range(n)])
ans = []
visited = [False for i in range(n)]
for i in range(n):
	if visited[i]:
		continue
	cur = i
	cyc = []
	while not visited[cur]:
		visited[cur] = True
		cyc.append(cur + 1)
		cur = x[cur][1]
	ans.append(cyc)
print(len(ans))
for cyc in ans:
	print(len(cyc), *cyc)


from collections import Counter, defaultdict, deque
import math
n = int(input())
arr = [int(x) for x in input().split()]
d = {}
visited = {}
for i in range(n):
	d[arr[i]] = i
	visited[arr[i]] = False
res = []
sarr = sorted(arr)
for el in sarr:
	cur = []
	nxt = el
	while True:
		if visited[nxt]:
			break
		visited[nxt] = True
		cur.append(d[nxt])
		nxt = sarr[d[nxt]]
	if len(cur):
		res.append(cur)
print(len(res))
for el in res:
	print(len(el), end=' ')
	for p in el:
		print(p + 1, end=' ')
	print()