Поиск цикла в перестановке с максимальной суммой

Python Сложный loops

Задача «Поиск цикла в перестановке с максимальной суммой»

Дана перестановка чисел от 1 до N. Рассмотрим ориентированный граф, где каждая вершина i имеет ребро к a[i]. Найдите цикл в этом графе, сумма элементов которого максимальна. Если таких циклов несколько, выведите любой. Гарантируется, что N ≥ 2. Циклом считается последовательность различных вершин, где каждая следующая вершина получается по правилу: следующая = a[текущая], и последняя вершина ребром возвращается к первой.

Формат ввода

Первая строка содержит целое число N (2 ≤ N ≤ 10^5). Вторая строка содержит N целых чисел a[1], a[2], ..., a[N] — перестановка чисел от 1 до N.

Формат вывода

Выведите два числа: длину цикла и сумму элементов цикла. Затем на следующей строке выведите элементы цикла в порядке обхода, начиная с любого элемента.

Примеры

Пример 1

ВВОД

5
2 3 1 5 4

ВЫВОД

2 9
4 5

Пример 2

ВВОД

7
1 2 3 4 5 6 7

ВЫВОД

1 7
7

Пример 3

ВВОД

4
abc
cde
xyz
zab

ВЫВОД

Invalid input

Пример 4

ВВОД

4
2 1 4 3

ВЫВОД

2 7
3 4

Пример 5

ВВОД

3
1 0 2

ВЫВОД

1 1
1

main.py