Bắn súng

Trong một buổi tập bắn súng, có \(N\) tấm bia được xếp thành một hàng dọc, đánh số từ \(1\) tới \(N\).
Độ bền ban đầu của tấm bia thứ \(i\) là \(A_i\).

Một tấm bia được coi là bị phá huỷ nếu độ bền của nó giảm xuống nhỏ hơn hoặc bằng \(0\) (khi đó coi độ bền của tấm bia là \(0\)).

Xạ thủ được quyền chọn một loại đạn có sức công phá \(X\) (với \(X\) là số nguyên dương) và dùng xuyên suốt cho toàn bộ buổi tập.

Mỗi lần bắn:

• Viên đạn trúng tấm bia đầu tiên chưa bị phá huỷ, tức là tấm bia có chỉ số nhỏ nhất \(i\) sao cho \(A_i>0\).
• Do đạn có tính xuyên phá, viên đạn gây ảnh hưởng lên tấm bia \(i\) và các tấm bia phía sau nó. Với mọi \(j\ge i\), độ bền của tấm bia \(j\) bị giảm một lượng $$ max(0,\;X-(j-i)^2). $$

Ví dụ minh hoạ

Với \(X=5\), có \(6\) tấm bia với độ bền lần lượt là \([0,2,5,0,1,2]\).
Viên đạn đầu tiên trúng vào tấm bia thứ \(2\) (vì tấm \(1\) đã có độ bền bằng \(0\)), và gây ảnh hưởng lên các tấm bia \(2,3,5,6\) (tấm \(4\) có độ bền bằng \(0\)).
Lượng độ bền bị giảm được tính như sau:

• Tấm bia thứ \(2\): \(\max(0,\,5-(2-2)^2)=\max(0,\,5-0^2)=5\).
• Tấm bia thứ \(3\): \(\max(0,\,5-(3-2)^2)=\max(0,\,5-1^2)=4\).
• Tấm bia thứ \(5\): \(\max(0,\,5-(5-2)^2)=\max(0,\,5-3^2)=0\).
• Tấm bia thứ \(6\): \(\max(0,\,5-(6-2)^2)=\max(0,\,5-4^2)=0\).

Vậy sau lượt bắn này, độ bền của các tấm bia là \([0,0,1,0,1,2]\).

Xạ thủ dừng lại khi một trong hai điều kiện xảy ra:

• Tất cả tấm bia đã bị phá huỷ; hoặc
• Đã bắn \(K\) lần.

Hãy tìm giá trị nhỏ nhất của \(X\) sao cho xạ thủ có thể phá huỷ toàn bộ \(N\) tấm bia khi bắn không quá \(K\) lần.

Input

Dòng đầu tiên chứa hai số nguyên dương \(N, K\) \((N\le 2\cdot 10^5,\; K\le 10^9)\).

Dòng thứ hai chứa \(N\) số nguyên dương \(A_1,A_2,\dots,A_N\) \((A_i\le 10^9)\).

Output

In ra một số nguyên dương là giá trị nhỏ nhất của \(X\).

Ví dụ

| standard input | standard output |
|—|—|
| 6 3 6 7 1 3 2 1 | 5 |
| 3 1 3 7 3 | 8 |

Ràng buộc

• Subtask 1 (30% số điểm): \(N,K \le 30,\; A_i \le 30\).
• Subtask 2 (20% số điểm): \(K = 1\).
• Subtask 3 (30% số điểm): \(N \le 1000\).
• Subtask 4 (20% số điểm): không có ràng buộc gì thêm.