Description

This is the easier version of this question. The only difference between the two versions is that this one has a smaller range of data.

Jiang Xinting is studying teleportation at QiLing University ( $QiLing \space Universsity, \space qlu$ ). The QiLing University's sacred animal, the Fire QiLing, will stimulate her studies with its powerful fire magic.

There are $n$ buildings in QiLing University, numbered $1, 2, \dots, n$, and the height of the $i$ building is $h_i$. The first $n - 1$ buildings will be set on fire, which means that only the $n$ building is safe. Jiang Xinting starts in the $1$ building, and she needs to teleport to the $n$ building.

Since Jiang Xinting's teleportation magic is very slow, she can only jump from $i$($1 \le i < n$) to $j$($i < j \le n$) if at least one of the following conditions is met.

• $i + 1 = j$
• $\max(h_{i + 1}, \ldots, h_{j - 1}) < \min(h_i, h_j)$
• $\max(h_i, h_j) < \min(h_{i + 1}, \ldots, h_{j - 1})$.

Jiang Xinting can't teleport too many times due to her lack of stamina from staying up late all night. She wants you to help her calculate the minimum number of teleports needed to reach the $n$th building.

Input

The first line is two integers $n(1 \le n \le 1000)$.

The second $n$ integer, $h_i$($1 \le h_i \le 10^9$), represents the height of each building.

Output

Output line with an integer indicating the minimum number of transmissions to reach the $n$th building.

Samples

5
1 3 1 4 5

``Output1 3

```Input2
4
4 2 2 4

1

Hints

In sample $1$, Jiang Xinting can be transmitted by the following path: $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$.