2025.05.08

Thuận và Ánh là đôi bạn thân. Hàng ngày họ liên lạc với nhau qua mạng xã hội, tuy nhiên do muốn gặp nhau, họ đã thử bước về phía nhau.

Có thể coi thế giới nơi Thuận và Ánh sống là một trục toạ độ Ox. Hiện tại, Thuận đang đứng ở vị trí \(x\) còn Ánh đang đứng ở vị trí \(y\). Thuận sẽ di chuyển với vận tốc là \(u\), còn Ánh sẽ di chuyển với vận tốc là \(v\). Khi hai người gặp nhau thì hai người sẽ dừng lại.

• Nếu vận tốc dương thì người đó đang đi cùng chiều Ox của trục toạ độ.
• Nếu vận tốc âm thì người đó đang đi ngược chiều Ox của trục toạ độ.

Yêu cầu: Hỏi sau ít nhất bao nhiêu giờ thì Thuận và Ánh gặp nhau?

Input

• Dòng thứ nhất chứa hai số nguyên \(x,u\) (\(-10^9 \le x,u \le 10^9\)).
• Dòng thứ hai chứa hai số nguyên \(y,v\) (\(-10^9 \le y,v \le 10^9\)).

Output

• Đưa ra một số nguyên duy nhất là kết quả bài toán. Nếu hai người không thể gặp nhau, đưa ra \(-1\).

Example

1 9
2 3

1

1 -4
3 -2

-1

Explanation

• Với ví dụ \(1\), sau \(10\) phút (hay \(\frac{1}{6}\) giờ), Thuận đi được thêm một đoạn độ dài \(\frac{9}{6} = 1.5\) và Ánh đi được thêm một đoạn \(\frac{3}{6} = 0.5\) nên hai người gặp nhau tại vị trí \(2.5\). Vậy nên sau ít nhất \(1\) giờ thì hai người gặp nhau.
• Với ví dụ \(2\), ta thấy cả hai người cùng đang đi ngược chiều Ox của trục tọa độ. Do Ánh đang đi về phía Thuận với tốc độ chậm hơn tốc độ Thuận rời xa Ánh nên Ánh sẽ không thể đuổi kịp Thuận và hai người không thể gặp nhau.

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}\).

Thuậ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\).

Nế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.

Hã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.

Input

• Dòng đầu tiên chứa một số nguyên dương \(n\) \((n \leq 10^{7})\).
• 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)\).

Dữ liệu bảo đảm tồn tại một đáp án hợp lệ.

Output

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

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 1000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^{5}\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^{6}\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

10 
10 1 2 0 3 4 5 0 2 10

2