Sau 7769 giờ lặn lội tìm kiếm The Hidden Gems, Tý đặt chân đến một hòn đảo hoang, nơi được đánh dấu là có kho báu. Tuy nhiên, để tới được chỗ kho báu được chôn thì không hề dễ dàng. Cụ thể, để bảo vệ The Hidden Gems, hòn đảo được Tèo giấu tên sắp xếp những tảng đá hình hộp chữ nhật một cách cực kỳ khó hiểu và ngẫu hứng nhằm ngăn cản bước tiến của Tý trong thử thách cuối cùng này. Nhưng với Tý thì dăm ba cái khoản leo trèo vốn là nghề của Tý, do đó Tý dương tự đắc, dự định nghỉ lại một đêm, rồi tối hôm sau sẽ xuất phát. Nhưng người tính không bằng trời tính, trời đổ mưa dữ dội, khiến cho vùng trũng của những tảng đá kia nay đã ngập nước. Với bản lĩnh của một hải tặc vô địch thiên hạ, đầu đội trời, chân đạp đất, Tý không biết bơi nên quyết định nhờ bạn tính toán lượng nước tối đa mà Tý sẽ gặp phải để Tý uống vừa đủ, không vượt quá 2 lít nước mỗi ngày trước khi tiếp cận được The Hidden Gems.

Cụ thể yêu cầu của Tý như sau: Có N hòn đá tảng với chiều cao h, trong đó h là một số không âm được đo đạc trước, với những nơi không có tảng đá nào, thì h = 0. Dựa trên những dữ kiện đó, bạn sẽ cần tính toán lượng mưa lớn nhất mà Tý sẽ gặp phải khi đi từ tảng đá đầu tiên đến tảng đá thứ N, biết sau tảng đá thứ N và trước tảng đá đầu tiên thì hoàn toàn là đất liền. Nơi có nước sẽ là vùng trũng nơi bị ngăn cách bởi các tảng đá ở hai bên (như hình minh họa bên dưới).

Input:

• Dòng đầu tiên chứa một số nguyên N duy nhất (0 < n ≤ 2 * 10^4)

• Dòng thứ hai bao gồm một mảng gồm N số nguyên không âm là chiều cao h của các tảng đá hình hộp chữ nhật (h ≤ 10^5)

Output: Một dòng duy nhất cho biết lượng nước lớn nhất có thể đọng lại trong các vùng trũng của các tảng đá.

Giới hạn: 0 < N ≤ 2 * 10^4; 0 < h ≤ 10^5

Testcase: Như hình minh họa.

Input 01:

12
0 1 0 2 1 0 1 3 2 1 2 1

Output 01:

6

Input 02:

6
4 2 0 3 2 5

Output 02:

9