문제1410--봉화

1410: 봉화

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 256 MB  제출 : 45  맞은 사람 : 6

제출  

문제 설명

전화나 인터넷이 없던 시절에는 사람이 직접 편지를 배달하여 정보의 전달이 늦었다.
그런데 다른 나라에서 쳐들어온다는 정보는 늦게 전달되면 나라가 위험해질 수 있기에 이를 해결하고자 봉화 시스템을 고안했다.
봉화는 산봉우리에 굴뚝을 설치하고 불을 피워 낮에는 연기로 밤에는 불빛으로 멀리서 군사 정보를 전달받을 수 있도록 만든 시스템이다.
수도에서 시야가 보일 수 있는 산봉우리에 봉화를 설치해야 정보의 전달을 할 수 있기에 그런 산봉우리에만 봉화를 설치할 수 있다.
수도에서 시야가 보일 수 있는 산봉우리는 해당 산봉우리와 수도 사이에 더 높은 산봉우리가 없는 산봉우리다.
예를 들어, 

위와 같이 산봉우리가 있을 때 4번의 산봉우리는 수도 사이에 더 높은 산봉우리가 없어 봉화를 설치할 수 있지만 3번의 산봉우리는 4번의 산봉우리 때문에 봉화를 설치할 수 없다.
마찬가지 이유로 2번에는 봉화를 설치할 수 있지만 1번에는 설치할 수 없다.
수도가 항상 오른쪽 끝에 있고 산봉우리의 높이가 주어질 때 봉화를 설치할 수 있는 산봉우리의 개수를 출력하는 프로그램을 작성하시오.

입력 설명

첫 번째 줄에 산봉우리의 개수를 나타내는 정수 N(1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄부터 N + 1번째 줄에 걸쳐 봉우리의 높이를 나타내는 정수 h(1 ≤ h ≤ 100,000)가 주어진다. 

출력 설명

봉화를 설치할 수 있는 산봉우리의 개수를 출력한다.

입력 예시1 Copy

4
4
5
2
3

출력 예시1 Copy

2

입력 예시2 Copy

6
6
5
2
4
3
2

출력 예시2 Copy

5

출처/분류