Это сложная версия задачи. Различие между версиями заключается в ограничениях на \(n\) и \(a_i\). Вы можете делать взломы, только если обе версии этой задачи сданы.
Сначала Aoi придумал следующую идею для задачи по программированию:
Yuzu девочка, которая коллекционирует конфеты. Изначально, у нее есть \(x\) конфет. Также есть \(n\) врагов, пронумерованных целыми числами от \(1\) до \(n\). Враг \(i\) имеет \(a_i\) конфет.
Yuzu хочет получить перестановку \(P\). Перестановкой называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\), расположенных в некотором порядке. Например, \(\{2,3,1,5,4\}\) это перестановка, а \(\{1,2,2\}\) это не перестановка (число \(2\) встречается в массиве дважды) и \(\{1,3,4\}\) тоже не является перестановкой (потому что \(n=3\), но в массиве есть число \(4\)).
После этого, она проведет \(n\) дуэлей с врагами по следующим правилам:
- Если Yuzu сейчас имеет не меньше конфет, чем враг \(P_i\), она побеждает в дуэли и получает \(1\) конфету. Иначе, она проигрывает дуэль и ничего не получает.
- Конфета, которую получает Yuzu в случае победы, будет использоваться в следующих дуэлях.
Yuzu хочет победить во всех дуэлях. Сколько существует возможных перестановок \(P\), для которых это произойдет?
Эта задача была простой и неинтересной для Akari, друга Aoi. И Akari придумал следующую задачу, на основе описанной идеи:
Давайте определим \(f(x)\) как количество возможных перестановок для целого числа \(x\).
Вам дано число \(n\), массив \(a\) и простое число \(p \le n\). Назовем целое положительное число \(x\) хорошим, если значение \(f(x)\) не делится на \(p\). Найдите все хорошие числа \(x\).
Решите задачу, предложенную Akari.
Выходные данные
В первой строке выведите количество хороших чисел \(x\).
Во второй строке выведите все хорошие числа \(x\) в возрастающем порядке.
Гарантируется, что количество хороших чисел \(x\) не превосходит \(10^5\).