Search for a cycle in a permutation with the maximum sum

Python Hard loops

Task «Search for a cycle in a permutation with the maximum sum»

Given a permutation of numbers from 1 to N. Consider a directed graph where each vertex i has an edge to a[i]. Find a cycle in this graph whose sum of elements is maximum. If there are several such cycles, output any of them. It is guaranteed that N ≥ 2. A cycle is a sequence of distinct vertices where each next vertex is obtained by the rule: next = a[current], and the last vertex returns to the first via an edge.

Input Format

The first line contains an integer N (2 ≤ N ≤ 10^5). The second line contains N integers a[1], a[2], ..., a[N] — a permutation of numbers from 1 to N.

Output Format

Output two numbers: the length of the cycle and the sum of the cycle's elements. Then, on the next line, output the elements of the cycle in traversal order, starting from any element.

Examples

Example 1

INPUT

5
2 3 1 5 4

OUTPUT

2 9
4 5

Example 2

INPUT

7
1 2 3 4 5 6 7

OUTPUT

1 7
7

Example 3

INPUT

4
abc
cde
xyz
zab

OUTPUT

Invalid input

Example 4

INPUT

4
2 1 4 3

OUTPUT

2 7
3 4

Example 5

INPUT

3
1 0 2

OUTPUT

1 1
1

main.py