Это — сложная версия задачи. В ней $$$1 \le n \le 10^6$$$ и $$$0 \leq a_i \leq 10^6$$$. Вы можете взламывать эту версию тогда, когда решите ее (но предыдущую только тогда, когда заблокировали обе версии).

Приближается Рождество, и наш главный герой, Боб, готовит эффектный подарок для своей давней лучшей подруги Алисы. В этом году он решил приготовить $$$n$$$ коробок шоколада, пронумерованных от $$$1$$$ до $$$n$$$. Изначально $$$i$$$-я коробка содержит $$$a_i$$$ кусочков шоколада.

Поскольку Боб — типичный приятный парень, он не отправит Алисе $$$n$$$ пустых ящиков. Другими словами, минимум одно число из $$$a_1, a_2, \ldots, a_n$$$ является положительным. Поскольку Алиса не любит взаимно простые множества, она будет счастлива, только если существует какое-то целое число $$$k > 1$$$, такое, что количество кусочков в каждой коробке делится на $$$k$$$. Обратите внимание, что Алиса не будет возражать, если будут какие-то пустые коробки.

Чарли, парень Алисы, также является вторым лучшим другом Боба, поэтому он решает помочь Бобу, переставляя кусочки шоколада. За одну секунду Чарли может взять кусок в $$$i$$$-й коробке, и поместить его либо в $$$i-1$$$-ю коробку или $$$i+1$$$-ю коробку (если такие коробки существуют). Конечно, он хочет помочь своему другу как можно быстрее. Поэтому он просит вас подсчитать минимальное количество секунд, которое понадобится ему, чтобы сделать Алису счастливой.