Числовий многокутник (Npolygon)
Якось до Дім Дімича в гості завітав його друг Васька. Вони разом готувалися до олімпіади з усного рахунку, а тому постійно додавали всі числа, які тільки бачили. Сімка вирішила допомогти друзям та намалювала N-кутник, до кожної з вершин якого приписала число. Васька, побачивши зображення, запропонував додавати не всі числа, а тільки k (1 < k < N), що йдуть підряд за годинниковою стрілкою. Дім Дімич запропонував не всім вершинам многокутника приписувати одне й те саме число. Друзі з подивом помітили, що при цьому іноді суми отримуються однаковими для всіх вершин. Вони позначили S(i,k) як суму чисел в k послідовних вершинах, починаючи з вершини i. Друзі вирішили знайти максимальне k, при якому всі такі суми рівні.
Формат введення-виведення:
Програма Npolygon зчитує з клавіатури (стандартного пристрою введення) єдине ціле число N кількість кутів N-кутника (3 ≤ N ≤ 1015).
Програма Npolygon виводить на екран (стандартний пристрій виведення) єдине число k (1 < k < N) – максимальну кількість чисел, що розташовані підряд за годинниковою стрілкою, серед яких хоча б два різних, таких, що для всіх i S(i,k) рівні між собою. Якщо таку послідовність чисел у заданого N-кутника написати немає можливості, виведіть «-1» (без лапок).
Приклад вхідних та вихідних даних
|
Введення |
Виведення |
|
6 |
4 |
|
9 |
6 |