첨탑 밀어서 부수기

면접 대비

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

요약

앞에서부터 첨탑을 밀어 모두 넘어뜨리는 데 필요한 밀기 횟수를 구합니다. 쓰러지는 첨탑이 뒤 첨탑보다 높을 때만 연쇄로 넘어갑니다.

난이도: 쉬움10점 중 3점
유형: 그리디, 구현
정답자: 아직 제출이 없습니다

문제

부산대학교 새내기 산지니는 일직선으로 뻗은 등굣길을 막고 있는 정체불명의 첨탑들을 밀어서 넘어뜨려 부수기로 했다. 첨탑은 일렬로 줄지어 서 있으며, 산지니가 앞에서 첨탑을 밀면 첨탑은 뒤로 넘어진다. 넘어지는 첨탑의 높이가 바로 다음 첨탑의 높이보다 클 때만 다음 첨탑도 넘어진다. 산지니가 모든 첨탑을 넘어뜨리려면 몇 번을 밀어야 하는지 구하여라. 산지니는 반드시 앞으로만 이동하며 길을 우회하지 않는다.

입력

첫째 줄에 첨탑의 개수 $N$ 이 주어진다. $(1 \leq N \leq 5\,000\,000)$

둘째 줄에는 앞에서부터 차례대로 첨탑의 높이 $H_1, H_2, \cdots, H_N$ 이 주어진다. $(1 \leq H_i \leq 1\,000\,000)$

입력으로 주어지는 모든 수는 정수이다.

출력

첫째 줄에 첨탑을 밀어야 하는 횟수를 출력한다.

예제2

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