{"code":"24tht255bc4","name":"Tiều phu","description":"Thuận là một bác tiêu phu lừng danh về tài năng chặt cây của mình. Hôm nay Thuận sẽ trồng và chặt một hàng cây gồm $n$ cây để lấy gỗ xây nhà mới cho mình, các cây được đánh số từ $1$ đến $n$ từ trái qua phải. Ở vị trí thứ $i$, Thuận chỉ được phép trồng cây có độ cao không quá $h_{i}$.\r\n\r\nThuận muốn tìm một loại cây có độ cao là số nguyên $k$ $(k \\leq h_{1}, k \\leq h_{n})$ và trồng vào một số vị trí thích hợp, biết rằng cậu chắc chắn sẽ trồng cây vào vị trí thứ $1$ và thứ $n$.\r\n\r\nNếu cây ở vị trí thứ $i$ ($i < n$) bị đổ, nó sẽ làm các cây ở vị trí trong khoảng $[i + 1, min(n, i + k)]$ đổ theo.\r\n\r\nHãy giúp Thuận tính xem, độ cao $k$ nhỏ nhất có thể là bao nhiêu, sao cho nếu Thuận chặt đổ cây ở vị trí thứ $1$ thì cây ở vị trí thứ $n$ cũng bị đổ theo.\r\n\r\n#### Input\r\n\r\n- Dòng đầu tiên chứa một số nguyên dương $n$ $(n \\leq 10^{7})$.\r\n- Dòng thứ hai chứa $n$ số nguyên không âm $h_{1}, h_{2}, \\ldots, h_{n}$ $(0 \\leq h_{i} \\leq n)$.\r\n\r\nDữ liệu bảo đảm tồn tại một đáp án hợp lệ.\r\n\r\n#### Output\r\n\r\n- In ra một số nguyên dương là kết quả của bài toán.\r\n\r\n#### Scoring\r\n\r\n- Subtask $1$ ($20\\%$ số điểm): $n \\le 100$.\r\n- Subtask $2$ ($20\\%$ số điểm): $n \\le 1000$.\r\n- Subtask $3$ ($20\\%$ số điểm): $n \\le 10^{5}$.\r\n- Subtask $4$ ($20\\%$ số điểm): $n \\le 10^{6}$.\r\n- Subtask $5$ ($20\\%$ số điểm): không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        10 \r\n        10 1 2 0 3 4 5 0 2 10\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        2\r\n        ```\r\n    ??? warning \"Note\"\r\n        Thuận trồng cây độ cao $2$ ở các vị trí $1, 3, 5, 7, 9, 10$.","points":800.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}