Problem Description

Bitaro, who enjoys home gardening, is growing a plant called Bibargrass in his backyard. There are $ N $ Bibargrass plants planted in a row from west to east, numbered from $ 1 $ to $ N $ in order from the west. Currently, the height of Bibargrass $ i $ ($1 \leq i \leq N$) is $ A_i $.

Due to a special breed improvement, each time water is given, the height of the plant increases by $ 1 $. Bitaro wants to water the plants multiple times to improve the appearance of his garden, aiming to satisfy the following conditions:

• Let $ B_i $ be the height of Bibargrass $ i $ ($1 \leq i \leq N$) after all watering sessions. There exists an integer $ k $ ($1 \leq k \leq N$) such that for $1 \leq j \leq k - 1$, $ B_j < B_{j + 1} $ and for $k \leq j \leq N - 1$, $ B_j > B_{j + 1} $.

However, Bitaro is clumsy and can only water a range of plants at once in each watering session. That is, each time he waters, he chooses integers $ L, R $ ($1 \leq L \leq R \leq N$) and waters Bibargrass $L, L + 1, \ldots, R$.

Bitaro wants to minimize the number of watering sessions.

Given the number of Bibargrass plants and their current heights, create a program to find the minimum number of watering sessions required to satisfy the conditions.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ N $ $ A_1 $ $\cdots$ $ A_N $

Output Format

Output the minimum number of watering sessions required to the standard output in one line.

Sample Input and Output

Sample Input #1

5
3 2 2 3 1

Sample Output #1

3

Sample Input #2

5
9 7 5 3 1

Sample Output #2

0

Sample Input #3

2
2021 2021

Sample Output #3

1

Sample Input #4

8
12 2 34 85 4 91 29 85

Sample Output #4

93

Notes/Hints

Constraints

• $2 \leq N \leq 200,000$.
• $1 \leq A_i \leq 1,000,000,000$ ($1 \leq i \leq N$).

Subtasks

1. ($ 40 $ points) $N \leq 2,000$.
2. ($ 60 $ points) No additional constraints.

Sample Explanation 1

The conditions can be satisfied by watering 3 times as follows:
- Water Bibargrass $ 2, 3, 4, 5 $ by choosing $ L=2 $ and $ R=5 $. The heights become $ 3, 3, 3, 4, 2 $.
- Water Bibargrass $ 2, 3 $ by choosing $ L=2 $ and $ R=3 $. The heights become $ 3, 4, 4, 4, 2 $.
- Water Bibargrass $ 3 $ by choosing $ L=3 $ and $ R=3 $. The heights become $ 3, 4, 5, 4, 2 $.
It is impossible to satisfy the conditions with 2 or fewer watering sessions, so the minimum number of sessions required is $ 3 $.

Sample Explanation 2

The conditions are already satisfied, so the minimum number of watering sessions required is $ 0 $.

Sample Explanation 3

To satisfy the conditions with one watering session, choose $ L=1 $ and $ R=1 $ to water Bibargrass $ 1 $ or choose $ L=2 $ and $ R=2 $ to water Bibargrass $ 2 $.

见题面 Input 部分

见题面 Output 部分