一片长长的牧场被划分为 $n$ 个连续的段，编号从 $1$ 到 $n$。第 $i$ 段草的初始高度为 $h_i$。每一段中都有一头牛在吃草。这些段之间由栅栏隔开。牛不能在段之间移动，但它们可以将头伸过栅栏，吃相邻段的草（对于每个 $1 \le i \le n-1$，第 $i$ 段和第 $i+1$ 段相邻）。

每一分钟，每头牛都会选择一个段来吃草：

• 如果牛所在的段还有草（$h_i > 0$），牛总是选择自己所在的段。
• 否则，牛会选择相邻段中仍然有草的段。
• 如果牛所在的段和相邻段都没有草，牛则什么也不做。

如果有 $x$ 头牛在同一段吃草，它们会在一分钟内将该段的草高度减少 $x$；不过草的高度不能低于零。因此，一分钟后，草的高度变为 $h_i := \max(0, h_i - x)$。

牛群会通力合作，以最快的速度吃完牧场上所有的草。请问它们需要多少分钟才能完成？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示牧场中段的数量。 第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$ ($0 \le h_i \le 10^9$)，表示连续各段草的初始高度。至少有一个 $h_i$ 的值大于零。

输出格式

输出一个整数，表示吃完所有草所需的最少分钟数。

样例

样例输入 1

5
5 4 0 4 6

样例输出 1

4

样例输入 2

3
1 4 6

样例输出 2

5

说明

在第一个样例中，最优策略如下：

• $[5, 4, 0, 4, 6]$ – 第 3 头牛选择相邻的第 4 段。其他牛在各自的段吃草。
• $[4, 3, 0, 2, 5]$ – 第 3 头牛选择第 4 段。
• $[3, 2, 0, 0, 4]$ – 第 3 头牛选择第 2 段，第 4 头牛选择第 5 段。
• $[2, 0, 0, 0, 2]$ – 第 3 头牛什么也不做；第 2 头牛选择第 1 段；第 4 头牛选择第 5 段。
• $[0, 0, 0, 0, 0]$ – 牛群在 4 分钟内吃完了所有的草。

在第二个样例中，牛群没有选择余地。过程必须如下进行： $[1, 4, 6] \to [0, 3, 5] \to [0, 1, 4] \to [0, 0, 3] \to [0, 0, 1] \to [0, 0, 0]$