Sau khi đánh bại nhiều đối thủ mạnh, Aiger Akabane muốn kích hoạt khả năng Infinite Evolution của Z Achilles.

Có \(n\) Beyblade được xếp thành một hàng. Beyblade thứ \(i\) có cấp độ là \(a_i\).

Nếu hai Beyblade kề nhau có cùng cấp độ, chúng sẽ hợp nhất thành một Beyblade mới có cấp độ tăng thêm \(1\).

Sau khi hợp nhất, hai Beyblade cũ biến mất và Beyblade mới được đặt vào đúng vị trí của chúng.

Quá trình trên được lặp lại cho đến khi không còn cặp Beyblade kề nhau nào có cùng cấp độ.

Hãy tìm cấp độ lớn nhất của bất kỳ Beyblade nào sau khi quá trình hợp nhất kết thúc.

Input

Dòng đầu tiên chứa số nguyên \(n\).

Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

Giới hạn

• \(1 \le n \le 2 \times 10^5\)
• \(1 \le a_i \le 10^9\)

Output

In ra một số nguyên duy nhất là cấp độ lớn nhất của bất kỳ Beyblade nào sau khi toàn bộ quá trình hợp nhất kết thúc.

Ví dụ

Input

3
1 1 2

Output

3

Giải thích

Ban đầu:

1 1 2

Hai Beyblade đầu tiên hợp nhất:

2 2

Tiếp tục hợp nhất:

3

Do đó đáp án là \(3\).