Это сложная версия задачи. Ключевое отличие между двумя версиями выделено жирным шрифтом.
Группа из \(n\) пауков собралась, чтобы обменяться плюшевыми игрушками. Изначально у каждого паука есть \(1\) плюшевая игрушка. Каждый год, если паук \(i\) имеет хотя бы одну плюшевую игрушку, он отдаст ровно одну плюшевую игрушку пауку \(r_i\). В противном случае он ничего не сделает. Обратите внимание, что все передачи плюшевых игрушек происходят одновременно. В этой версии каждому пауку разрешено иметь более 1 плюшевой игрушки в любой момент времени.
Процесс считается стабильным в текущем году, если у каждого паука такое же количество плюшевых игрушек (до обмена в текущем году), как и в предыдущем году (до обмена в предыдущем году). Обратите внимание, что год \(1\) никогда не может быть стабильным.
Найдите первый год, в котором процесс становится стабильным.
Выходные данные
Для каждого набора входных данных выведите целое число в новой строке, первый год, в котором процесс становится стабильным.
Примечание
Для второго набора входных данных:
- В год \(1\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 1, 1, 1, 1]\). Затем происходит обмен в год \(1\).
- В год \(2\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 1, 1, 1, 1]\). Поскольку этот массив такой же, как в предыдущем году, этот год является стабильным.
Для третьего набора входных данных:
- В год \(1\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 1, 1, 1, 1]\). Затем происходит обмен в год \(1\).
- В год \(2\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 2, 1, 1, 0]\). Затем происходит обмен в год \(2\).
- В год \(3\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 3, 0, 1, 0]\). Затем происходит обмен в год \(3\).
- В год \(4\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 4, 0, 0, 0]\). Затем происходит обмен в год \(4\).
- В год \(5\) следующий массив показывает количество плюшевых игрушек у каждого паука: \([1, 4, 0, 0, 0]\). Поскольку этот массив такой же, как в предыдущем году, этот год является стабильным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
2 1
5
2 3 4 5 1
5
2 1 4 2 3
5
4 1 1 5 4
10
4 3 9 1 6 7 9 10 10 3
|
2
2
5
5
5
|