Лёша участвует в съёмке очередного ролика BrMeast, и BrMeast попросил Лёшу подготовить 250 тысяч тонн тротила, но Лёша его не расслышал, поэтому он подготовил \(n\) коробок. Лёша хочет погрузить эти коробки в грузовики, для этого он расставил их в ряд, \(i\)-я слева коробка имеет вес \(a_i\) тонн.
Все грузовики, которые собирается использовать Лёша, вмещают в себя одинаковое количество коробок, обозначим это количество \(k\). Тогда погрузка происходит следующим образом:
- В первый грузовик помещаются первые \(k\) коробок,
- Во второй грузовик помещаются вторые \(k\) коробок,
- \(\dotsb\)
- В \(\frac{n}{k}\)-й грузовик помещаются последние \(k\) коробок.
По окончании погрузки в каждом грузовике должно быть ровно \(k\) коробок. То есть, если в какой-то момент в грузовик не получится загрузить ровно \(k\) коробок, то вариант погрузки с таким \(k\) невозможен.
Лёша ненавидит справедливость, так что он хочет, чтобы максимальная абсолютная разница между суммарным весом каких-либо двух грузовиков была как можно больше. Если грузовик один, эта величина равна \(0\).
У Лёши есть достаточно много связей, поэтому для каждого \(1 \leq k \leq n\) он может найти такую компанию, что каждый её грузовик вмещает в себя ровно \(k\) коробок. Выведите максимальную абсолютную разницу между суммарным весом каких-либо двух грузовиков.
Выходные данные
Для каждого набора данных выведите одно число — ответ на задачу.
Примечание
В первом случае выгодно взять два грузовика, в первом будет только первая коробка, во втором только вторая.
Во втором случае выгодно взять шесть грузовиков, в каждом по одной коробке. Тогда максимум равен \(10\), минимум равен \(1\), ответ равен \(10 - 1 = 9\).
В третьем случае при любом возможном \(k\) в грузовиках будет одинаковый суммарный вес коробок, то есть ответ равен \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
1 2
6
10 2 3 6 1 3
4
1000000000 1000000000 1000000000 1000000000
15
60978 82265 78961 56708 39846 31071 4913 4769 29092 91348 64119 72421 98405 222 14294
8
19957 69913 37531 96991 57838 21008 14207 19198
|
1
9
0
189114
112141
|