무거운 블록

시간 제한1초메모리 제한128 MB

요약

무게가 서로 다른 n개의 블록을 한 방향으로 밀어 가벼운 이웃 블록을 연쇄로 쓰러뜨릴 때 모든 블록을 쓰러뜨리는 최소 푸시 횟수를 구합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 스택, 트리, 분할 정복
정답자: 아직 제출이 없습니다

문제

$n$ 개의 블록이 한 줄로 세워져 있고, 왼쪽부터 차례로 놓여 있다. 각 블록의 무게는 서로 다른 양의 정수이다.

세워져 있는 블록 하나를 왼쪽이나 오른쪽으로 밀면 그 블록이 넘어진다. 넘어짐은 도미노처럼 민 방향으로 퍼지며, 민 블록보다 가벼운 블록을 연속으로 넘어뜨린다. 민 블록보다 무거운 블록을 만나면(그 무거운 블록은 넘어지지 않고 그대로 서 있다) 또는 이미 넘어진 자리에 도달하면 거기서 멈춘다. 민 블록 자신은 항상 넘어진다.

한 번의 밀기는 서 있는 블록 하나를 한 방향으로 미는 것이다. 모든 블록을 넘어뜨리는 데 필요한 최소 밀기 횟수를 구하여라.

입력

첫 번째 줄에 블록의 개수 $n$ 이 주어진다 ( $1 \le n \le 10^6$ ).

두 번째 줄에 왼쪽부터 차례로 각 블록의 무게를 나타내는 서로 다른 정수 $n$ 개가 주어지며, 각 값은 $1$ 이상 $10^9$ 이하이다.

출력

모든 블록을 넘어뜨리는 데 필요한 최소 밀기 횟수를 한 줄에 출력한다.

예제3

예제 1
입력
```
7
3 5 7 2 1 6 4
```
예상 출력
```
2
```
예제 2
입력
```
1
5
```
예상 출력
```
1
```
예제 3
입력
```
2
1 2
```
예상 출력
```
1
```