30026번 - 차원문 스페셜 저지

문제

차원문은 매우 편리한 교통수단이다. 차원문은 평범한 문처럼 생겼지만, 문을 열고 들어가면 다른 공간으로 이동할 수 있는 특별한 성질이 있다. 단, 반대 방향으로 차원문을 이용할 수는 없다. ANA 나라에는 $N$개의 도시가 있다. 각각의 도시는 1,2,ドル\cdots ,N$번으로 번호가 매겨져 있다. 차원문을 다루는 차원술사 인수는 1,2,ドル\cdots ,N$번 도시로 이동할 수 있는 차원문을 만들고 각각의 차원문에 1,2,ドル\cdots ,N$번으로 번호를 매겼다. 그리고 이를 $N$개의 도시에 하나씩 무작위로 설치했는데, $i$번 도시에 설치한 차원문의 번호는 $a_i$번이고 이는 $a_i$번 도시로 향하는 차원문이다.

그런데, 인수는 임의의 한 도시에서 차원문만을 이용해서 다른 모든 도시를 방문하는 것이 불가능할 수도 있다는 것을 알게 되었다. 그래서 인수는 임의의 서로 다른 두 도시를 선택한 후에 두 도시의 차원문을 서로 바꾸는 마법을 몇 번 사용해서 이를 해결하려고 한다. 인수가 마법을 사용하기 위해서는 마나가 필요한데, 서로 다른 두 도시의 차원문을 바꾸는 마법을 사용하려면 두 차원문의 번호 차의 제곱만큼 마나가 필요하다. 예를 들어, 1ドル$번 도시에 설치된 차원문이 4ドル$번 도시로 향하는 4ドル$번 차원문이고, 4ドル$번 도시의 차원문이 6ドル$번 도시로 향하는 6ドル$번 차원문이라면 두 도시의 차원문을 바꾸기 위해서는 $(4-6)^2=4$만큼의 마나가 필요하다.

임의의 한 도시에서 차원문만을 이용해서 다른 모든 도시를 방문하는 것이 가능하게 만들기 위해 필요한 최소 마나를 구해보자. 그리고 어떻게 마법을 사용해야 하는지도 구해보자. 단, 마법을 사용하는 횟수가 최소일 필요는 없다.

입력

첫째 줄에 정수 $N(2\le N\le 200,円 000)$이 주어진다.

둘째 줄에 정수 $a_1,a_2,\cdots ,a_N(1\le a_i\le N)$이 공백으로 구분되어 주어진다.

출력

첫째 줄에 필요한 최소 마나 $C$와 마법을 사용하는 횟수 $M$을 공백으로 구분하여 출력한다. 마법을 사용하는 횟수가 최소일 필요는 없다.

둘째 줄부터 $M$개의 줄에 순서대로 차원문을 바꿔야 하는 두 도시의 번호를 공백으로 구분하여 출력한다.

제한

힌트