Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P142PROJ - ROUND 2J - Hệ thống mê cung

Tèo nằm mơ thấy mình trở thành giám đốc của Công viên Thủ lệ. Để cho công viên thêm phần thú vị, Tèo quyết định đầu tư xây dựng một mê cung dài loằng trong công viên, nó gồm hệ thống các phòng tham quan trên mặt đất, và hệ thống đường đi ngầm dưới lòng đất. Tổng công trình sư cho hệ thống này, không ai khác, chính là người bạn thân của Tèo, kĩ sư Tí.

Có n phòng tham quan nổi trên mặt đất, mỗi phòng mang một số hiệu riêng a_i. Lối vào bắt đầu ở phòng có số hiệu nhỏ nhất, và lối ra ở phòng có số hiệu lớn nhất. Kĩ sư Tí quyết định thiết kế như sau: sẽ đào đường hầm tham quan 2 chiều giữa 2 phòng mang số hiệu x và y, nếu chúng có ước chung lớn hơn 1. Lưu lượng người tối đa có thể di chuyển trong đường hầm này bằng UCLN(x,y) người/1 phút (lưu lượng tối đa chiều đi = lưu lượng tối đa chiều về = UCLN(x,y)). Khách tham quan một khi bị lạc vào mê cung rồi, sẽ đi liên tục trong hệ thống mê cung này.

Sau khi xem qua bản thiết kế của Tí, Tèo đã yêu cầu Tí tính toán xem số lượng người tối đa có thể tham quan mê cung sao cho hệ thống đường hầm giao thông này không bị tắc nghẽn?

Input

Dòng đầu tiên là số nguyên dương n (2 <= n <= 1000) là số phòng của hệ thống mê cung.

n dòng tiếp theo, mỗi dòng gồm một số nguyên là số hiệu của phòng thứ i. Giá trị này nằm trong đoạn [2, 2*10^9].

Output

In ra lưu lượng người lớn nhất có thể vào mê cung/phút. (Lưu lượng tối đa là 10^9 người/phút).

Example

Test 1:

Input:

4
4
6
8
9

Output:

3

 

Test 2:

Input:

7
25289
17017
2601
325
225
55223
190969

Output:

18


Được gửi lên bởi:adm
Ngày:2014-02-08
Thời gian chạy:5s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2014-06-07 03:54:56 Hướng Thái Dương
luồng :))
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.