Cho mảng ~A~ gồm ~n~ số nguyên.

Bạn phải thay đổi ít nhất bao nhiêu số để mảng ~A~ chỉ gồm các số nguyên liên tiếp?

Input

• Dòng đầu tiên gồm số nguyên ~n~.
• Dòng thứ hai gồm ~n~ số nguyên ~A_i~.

Output

• In ra số lượng số nguyên ít nhất phải thay.

Điều kiện

• ~1 \le n \le 10^5~.
• ~1 \le A_i \le 10^9~.

Ví dụ

Input:

3
4 10 5

Output:

1

Chú ý: Thay ~10~ bằng ~6~.

Ràng buộc

• Subtask 1 ~(50\%)~: ~n \le 1000~.
• Subtask 2 ~(50\%)~: Không có ràng buộc gì thêm.

Sin-ga-lore là đất nước giáo dục lý tưởng cho nhiều học sinh đội tuyển. Ở Sing, anh Quân nổi tiếng là một học sinh giỏi đã học ~N~ môn học. Mỗi môn thứ ~i~ anh Quân được ~A_i~ điểm. Tại đây, điểm số là một số nguyên từ ~1~ đến ~5~. Điểm trung bình của mỗi học sinh là tổng điểm các môn chia cho số môn đã học (i.e. ~\frac{\sum_{i=1}^{n} A_i}{N}~) và làm tròn đến số nguyên gần nhất (Ví dụ: ~4.4~ sẽ làm tròn xuống ~4.0~, ~4.5~ sẽ làm tròn lên ~5.0~, hay ~3.49~ sẽ làm tròn xuống ~3.0~). Vì có nhiều đệ của anh Quân sang NUS học nên trường đã tặng cho anh Quân một món quà. Trường sẽ cho phép anh Quân sửa đổi tùy ý một vài điểm số bất kì. Tất nhiên là điểm đó phải hợp lệ (tức là một số nguyên từ ~1~ đến ~5~). Hỏi anh Quân sẽ phải sửa điểm của ít nhất bao nhiêu môn học để có điểm trung bình là ~5.0~

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~.
• Dòng thứ hai gồm ~N~ số nguyên dương miêu tả dãy ~A~, dữ liệu đảm bảo rằng đây đều là các số nguyên dương từ ~1~ đến ~5~.

Output:

• In ra một số nguyên không âm là kết quả của bài toán.

Subtask:

• Subtask ~1~ (~30\%~ số điểm): ~N \le 9~.
• Subtask ~2~ (~70\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

4
3 2 5 4

Sample Output 1

2

Cho dãy số có quy luật như sau: ~1,2,2,3,3,3,4,4,4,4,5,5,…~ Cho một số tự nhiên ~N~, hãy tìm số thứ ~N~ của dãy số trên (các số được đánh thứ tự từ ~1~).

Input

• Gồm một số nguyên dương ~N~ ~(N ≤ 10^{15})~.

Output

• In ra kết quả của bài toán.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~N ≤ 10^{6}~;
• Subtask 2 (~20\%~ số điểm): ~N ≤ 10^{10}~;
• Subtask 3 (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5

Output

3

Cho một dãy số nguyên dương gồm n phần tử ~a_1, a_2, \ldots, a_n~. Trọng số ~W~ của dãy ~a~ được định nghĩa là ước chung lớn nhất của tất cả các phần tử trong dãy, tức là ~W = \gcd(a_1, a_2, \ldots, a_n)~.

Ở đây, ~gcd~ được định nghĩa là phép lấy ước chung lớn nhất.

Bạn được phép thay đổi tối đa hai phần tử bất kỳ trong dãy ~a~ thành hai số nguyên dương khác sao cho trọng số mới của dãy đạt giá trị lớn nhất có thể.

Nhiệm vụ của bạn là tìm giá trị lớn nhất có thể của trọng số mới.

Dữ liệu vào từ tệp văn bản: THAYDOISO.INP

• Dòng đầu tiên gồm số nguyên dương ~n~ (~3 \le n \le 2 \cdot 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).

Kết quả ghi ra tệp văn bản: THAYDOISO.OUT

• Gồm số nguyên dương duy nhất là giá trị lớn nhất có thể của trọng số mới sau khi thay đổi tối đa hai phần tử trong dãy ~a~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N = 3~.
• Subtask ~2~ (~30\%~ số điểm): ~N, a_i \le 1000~.
• Subtask ~3~ (~30\%~ số điểm): ~N, a_i \le 10^5~.
• Subtask ~4~ (~10\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input 1

3
4 4 12

Sample Output 1

12

Sample Input 2

5
6 1 9 2 12

Sample Output 2

3

Explanation

Ở ví dụ thứ nhất, ta thay hai phần tử ~a_1~ và ~a_2~ thành giá trị ~12~.

Ở ví dụ thứ hai, ta thay hai phần tử ~a_2~ và ~a_4~ thành giá trị ~3~.

Cho số nguyên dương ~n~ và ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Tìm vị trí ~k~ sao cho chênh lệnh giữa tổng từ ~a_1~ đến ~a_k~ và tổng từ ~a_{k+1}~ đến ~a_n~ là nhỏ nhất ~(1 \le k < n)~.

Input

Dòng 1: Số nguyên dương ~n~ ~(n \le 10^5)~

Dòng 2: ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i<=10^9~)

Output

Ghi ra 2 số nguyên là chênh lệnh nhỏ nhất và vị trí ~k~. Nếu có nhiều vị trí ~k~ thỏa mãn thì chọn ~k~ nhỏ nhất.

Sample

Input

4
1 2 3 5

Output

1 3

Cho một xâu gồm ~m~ loại kí tự khác nhau (chỉ bao gồm các chữ cái tiếng Anh in hoa) và hai loại thao tác xoá như sau:

• Thao tác ~1~: Xoá kí tự đầu hoặc kí tự cuối của xâu;
• Thao tác ~2~: Xoá một kí tự ở giữa xâu.

Yêu cầu: Cho xâu ~S~ gồm ~N~ kí tự, hãy tìm cách sử dụng các thao tác xoá xâu để thoả mãn các điều kiện sau:

• Dùng tối thiểu thao tác ~2~;
• Xâu còn lại chỉ còn đúng ~m \times k~ kí tự;
• Mỗi loại kí tự chỉ xuất hiện đúng ~k~ lần.

Dữ liệu vào từ tệp văn bản DELSTR.INP:

• Dòng đầu tiên chứa hai số ~m, k~ ~(2 \le m \le 26)~;
• Dòng tiếp theo chứa xâu ~S~ ~(2 \le m \times k \le N \le 2 \times 10^5)~.

Kết quả ghi ra tệp văn bản DELSTR.OUT:

Gồm một số nguyên duy nhất là số thao tác ~2~ ít nhất được sử dụng để thoả mãn yêu cầu đề bài.

Ví dụ

Input

3 2
ABBABCABBCCCBA

Output

1

Giải thích

• Sử dụng thao tác ~1~: Xoá ~3~ kí tự đầu và ~4~ kí tự cuối.
• Sau đó dùng ~1~ lần thao tác ~2~ xoá kí tự ~B~ còn thừa ở giữa.

~\Rightarrow~ Thu được xâu: ABCABC thoả mãn có đúng ~3 \times 2 = 6~ kí tự và mỗi kí tự xuất hiện đúng ~2~ lần.

Input

3 2
ABABAAACCC

Output

2

Giải thích

• Xoá ~1~ kí tự đầu và ~1~ kí tự cuối, sau đó dùng hai lần thao tác ~2~ xoá kí tự ~A~ còn thừa ở giữa.

Ràng buộc

• Có ~25\%~ số test ứng với ~25\%~ số điểm có ~N \le 20~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~N \le 100~;
• ~25\%~ số test khác ứng với ~25\%~ số điểm có ~N \le 5000~;
• ~25\%~ số test còn lại ứng với ~25\%~ số điểm không có ràng buộc gì thêm.