405305: GYM101879 B Aesthetics in poetry

One of the greatest poets in Portuguese language was Luiz Vaz de Camões, born in Lisbon circa 1524. Camões works are fundamental reading for high school students in countries such as Brazil or Portugal. Many consider his 5- and 7-syllable poems and his sonnets (with 14 verses) to be the most important lyrical work in Portuguese of all time.

Camões was a visionary in his own time. His work has been studied from many aspects: historical, cultural, symbolical, and so on. Carlitos "the efficient" Nunes is studying aesthetics in Camões' poetry. He is especially interested in a metric based on the size of the verses of a poem. We define this metric as follows. Suppose we have a poem made of $$$N$$$ verses. We say that the poem is $$$K$$$-elegant if $$$K > 1$$$, $$$N$$$ is a multiple of $$$K$$$ and, moreover, there are exactly $$$N/K$$$ verses whose sizes, when divided by $$$K$$$, have remainders equal to $$$i$$$, for $$$i=0,1, \ldots, K-1$$$. Note that a single poem may be $$$K$$$-elegant for several distinct values of $$$K$$$.

Carlitos already processed the data from poems by Camões and now he needs your help to determine the smallest elegance in each of the poems.

The input has two lines. The first line has an integer $$$N$$$, the number of verses in the poem. In the second line you are given $$$N$$$ integers, say $$$\ell_1, \ell_2, \ldots, \ell_N$$$, such that $$$\ell_i$$$ represents the size of the $$$i$$$th verse of the poem.

Constraints

• $$$1 \leq N \leq 2 \cdot 10^3$$$
• $$$1 \leq \ell_i \leq 10^9$$$

A single integer $$$K$$$, the smallest integer such that the poem is $$$K$$$-elegant. If no such integer exists, print "-1".

6
3 6 1 7 8 14

2

5
17 21 14 35 13

5

In the first case, if $$$K = 2$$$, then $$$6, 8$$$ and $$$14$$$ (respectively, $$$3$$$, $$$1$$$ and $$$7$$$) have remainder $$$0$$$ (respectively, remainder $$$1$$$) when divided by $$$K$$$.