Cá mập

Trong $n$ ngày liên tiếp, người ta ghi lại quãng đường một con cá mập di chuyển mỗi ngày. Ngày thứ $i$ nó đi được quãng đường $a_i$, và tất cả các giá trị $a_i$ đều đôi một khác nhau.

Giả sử tồn tại một số nguyên $k$ với ý nghĩa như sau: trong ngày mà cá mập đi quãng đường nhỏ hơn $k$ thì nó ở yên tại một địa điểm; ngược lại, trong ngày mà nó đi quãng đường lớn hơn hoặc bằng $k$ thì nó đang di chuyển để đổi địa điểm (một lần đổi địa điểm có thể kéo dài qua nhiều ngày liên tiếp).

Như vậy, với một giá trị $k$ cố định, dãy các ngày được chia thành những đoạn liên tiếp: mỗi đoạn tối đa gồm những ngày liên tiếp mà quãng đường đi được đều nhỏ hơn $k$, và mỗi đoạn (khác rỗng) tương ứng với một địa điểm. Số địa điểm chính là số đoạn như vậy.

Hãy chọn số nguyên $k$ sao cho:

1. Tất cả các đoạn (địa điểm) có độ dài bằng nhau;
2. Số địa điểm là lớn nhất trong các $k$ thỏa mãn điều kiện 1;
3. $k$ nhỏ nhất trong các $k$ thỏa mãn cả hai điều kiện trên.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$: số ngày.
• Dòng thứ hai chứa $n$ số nguyên dương đôi một khác nhau $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

In ra một số nguyên $k$ thỏa mãn ba điều kiện trên.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le a_i\le {10}^9$
• Các $a_i$ đôi một khác nhau.

Ví dụ