After five years, Eloi is visiting grandma again. She is very proud because he has, by now, mastered the craft of sewing buttons. Eloi is about to finish his degree in math at the Academy of Colombian Mathematicians (ACM); as a matter of fact, he just defended his dissertation about arrangements of colored buttons. Grandma is currently into baking cakes of all sorts and flavors. “C is for cake; that’s good enough for me... fresh from the oven!” Well, for Eloi, C means programming contests, sleepless nights, and humongous cups of Colombian coffee. Anyway, he’s here to take a break from that and relax baking cakes with granny. Grandma usually bakes her cakes in baking pans which were once round, but due to carelessness and time, now have several dents all along their border. Eloi just can’t stop thinking about mathematics, so he has realized that there is an interesting geometrical puzzle related to the cakes. Given a circular baking pan with n dents on its border, what is the largest m such that there are m dents amongst the n which form a regular m-gon? Input The input consists of several test cases. Each test case consists of two lines. The first line of a test case contains an integer n (3 ≤ n < 103) indicating the number of dents in the border of the baking pan. The second line contains n blank-separated integers a1, . . . , an (with 1 ≤ ai ≤ 105): ai indicates the length of the arc between the ith dent and the next. Output For each test case output a line with the largest m such that there are m dents amongst the n that form a regular m-gon. If such an m does not exist, then output ‘-1’. Sample Input 3 111 3 121 4 2112 5 21122 5 11311 5 11211 Sample Output 3 -1 3 4
2/2 -1 3