**S. 87.** A group called Reformers of Mathematics made a huge discovery and created a new definition. The New Greatest Common Divisor, henceforth abbreviated as ngcd, of a finite sequence of natural numbers is defined as the number of elements of the sequence multiplied by the old-fashioned gcd of the sequence. The Reformers of Mathematics immediately give you the following task.

You are given a sequence of positive integers (*a*_{1},...,*a*_{N}) with . Determine the maximal possible ngcd over all subsequences formed by any consecutive elements of the original sequence.

Your program should read the value of *N* from the first line of the standard input, then the numbers *a*_{i} (1*a*_{i}10^{11}) from the next line. The first and only line of the standard output should contain the maximal positive integer that represents the ngcd of a connected subsequence of the given sequence.

In the example, ``Példa bemenet'' and ``Példa kimenet'' denote a sample input and output, respectively.

*Scoring and bounds.* You can obtain 1 point for a brief and proper documentation clearly describing your solution. Nine further points can be obtained provided that your program solves any arbitrary valid input within 1 second of running time. Partial points can be obtained if your program yields a solution for *N*200, or for *N*5000.

The source code (`s87.pas`, `s87.cpp`, ...) without the `.exe` or any other auxiliary files generated by the compiler but with a short documentation (`s87.txt`, `s87.pdf`, ...), also describing which developer environment to use for compiling the source, should be submitted in a compressed file `s87.zip`.

(10 points)

**Deadline expired on 10 March 2014.**

Mintamegoldásnak Somogyvári Kristóf megoldását tesszük közzé. A feladatnak ez az ismert leggyorsabb megoldása, intervallumfával - okosan lehet kicsit lassabbat, illetve nem olyan nagyon okosan kb 10-ed ilyen lassút. S87.zip