Một thành phố nọ có \(n\) toà nhà, toà nhà thứ \(i\) sẽ có chiều cao là \(a_{i}\). Thành phố hiện tại đang bị ngập lụt, mỗi ngày, chiều cao của mực nước sẽ dên lên thêm một tầng. Một toà nhà được xem là bị ngập hoàn toàn nếu như chiều cao của mực nước cao hơn chiều cao của toà nhà. Một toà nhà được gọi là đơn độc nếu như những toà nhà này chưa bị ngập hoàn toàn và những toà nhà nằm hai bên của nó nếu đã bị nhập hoàn toàn. Hãy tìm ra thời điểm mà có nhiều toà nhà đơn độc nhất thành phố.

Yêu cầu: Hãy in số lượng toà nhà đơn độc nhiều nhất mà bạn tìm được.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n\) \((1 \leq n \leq 10^{5})\) là số lượng toà nhà.
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{18})\) là chiều cao của các toà nhà.

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \leq a_{i}, n \leq 10^{3}\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq a_{i}, n \leq 10^{5}\).
• Subtask \(3\) (\(40\%\) số điểm): Không có giới hạn gì thêm.

Example

5
2 5 1 4 5

2