Vào một ngày đẹp trời, do nqson quá non nên laptop của nqson đã bị đính 1 loại virus mang tên uosbu. Loại virus này đã làm cho máy tính của nqson bị khóa hết tài liệu và yêu cầu nqson phải trả tiền để lấy mật khẩu mở khóa. May thay, nqson đã tìm ra một đoạn code trong con virus này và có thể dựa vào nó để tìm ra mật khẩu phá giải con virus đó.

Trong virus uosbu lưu 1 dãy số nguyên dương \(a_1, a_2, a_3,...a_n\). Mật khẩu của virus là số nguyên dương bé nhất mà hàm số dưới đây có thể tạo ra:

\[a_1*k_1+a_2*k_2+a_3*k_3+...+a_n*k_n\]

Với \(k_1,k_2,k_3,...k_n\) là các số nguyên không xác định.

Ví dụ với dãy số \(10, 5, 8, 24\) ta có:

\[~10*(-1) + 5*(-1) + 8*(-1) + 24*1 = 1~\]

hoặc

\[~10*0 + 5*5 + 8*0 + 24*(-1) = 1~\]

\(\to\) \(1\) là số nguyên dương bé nhất mà dãy số này có thể tạo ra, cũng chính là mật khẩu để phá giải virus uosbu chết tịt này.

Do rất rất rất và rất khó để tìm ra các con số \(k\) bị ẩn này, mà laptop của nqson vẫn đang bị dính virus uosbu, các bạn hãy code giúp nqson tìm mật khẩu nhé.

Đầu vào

Dòng đầu tiên chứa một số tự nhiên \(n\) là số phần tử của dãy số.

Dòng tiếp theo chứa \(n\) số nguyên \(a_1,a_2,a_3,...,a_n\) là các phẩn tử trong dãy số.

Đầu ra

In ra số nguyên dương duy nhất là mật khẩu của virus uosbu.

Giới hạn

\(20\%\): \(n \le 10; a_i \le 100\)

\(30\%\): \(n \le 1000; a_i \le 1000\)

\(50\%\): \(n \le 10^5; a_i \le 10^{18}\)

Ví dụ

Đầu vào:

4
10 5 8 24

Đầu ra:

1