Hi.
I want to solve a question. I know how to solve it but I want a better way to solve it. in first line number n is given and in second line, n numbers is given. We call value of i-th number as P_i. For the i-th number and j-th number, if (i - j) (P_i - P_j) < 0 is true, then there is edge between i and j in graph. (graph is undirected)
We want to find connected component of graph and print vertices in each connected component.

Input 1:
4
2 3 1 4
Output 2:
2
3 1 2 3
1 4
(output: print number of connected component, then each line, first print number of vertices in that component, then print vertices in increasing order)

Memory limit: 128MB
Time limit: 1 second
1 <= n <= 1000000

I noticed that the property, is property for checking inversion in an array. However the nlogn approach is only for count inversions but if I want to find them, then I need linear search in merge each time and so,my algorithm is not nlogn anymore.
There is two approach for find components. one of them is DFS and other is Disjoint set how every we want to print connected component so I thick that I couldn't use Disjoint set.
because of time limit and memory limit, I didn't know a best way.
Is it possible to help me or give me a idea?
Thanks.