고층 건물
면접 대비시간 제한2초메모리 제한128 MB
한 줄로 늘어선 N개 빌딩의 높이가 주어질 때, 한 빌딩에서 다른 빌딩들이 시야를 가리지 않고 보이는 개수의 최댓값을 구합니다.
문제
한 도시에 고층 건물 N개가 일렬로 서 있다. i번째 건물은 x=i인 위치에서 바닥 (i, 0)부터 지붕 (i, 높이_i)까지 이어지는 세로 선분으로 나타낸다.
한 건물 A의 지붕에서 다른 건물 B의 지붕으로 그은 선분이 A와 B를 제외한 어떤 건물도 지나거나 접하지 않으면, A에서 B를 볼 수 있다고 한다.
각 건물에서 볼 수 있는 다른 건물의 수를 셀 때, 그중 최댓값을 구하라.
입력
첫째 줄에 건물의 수 N이 주어진다. N은 1 이상 50 이하인 자연수이다.
둘째 줄에는 1번 건물부터 N번 건물까지의 높이가 공백으로 구분되어 주어진다. 각 높이는 1 이상 1,000,000,000 이하인 자연수이다.
출력
한 건물에서 볼 수 있는 다른 건물 수의 최댓값을 출력한다.