달리기
면접 대비시간 제한1초메모리 제한256 MB
각 주자에 대해 앞선 주자들 중 능력치가 더 높은 사람 수에 1을 더한 값을 최대값을 추적하며 구하는 문제입니다.
문제
장거리 달리기 대회에서 모든 선수가 반환점을 지난 상태이다. 어떤 선수의 앞에 있는 선수 중 평소 실력이 더 좋은 선수는 남은 거리 동안 앞지를 수 없다. 반대로, 평소 실력이 더 낮은 선수가 앞에 있다면 앞지를 수 있다고 가정한다.
각 선수의 평소 실력은 서로 다른 정수로 주어지며, 값이 클수록 실력이 좋다. 현재 달리고 있는 순서가 앞에서 뒤 순서로 주어질 때, 각 선수가 남은 거리 동안 얻을 수 있는 가장 좋은 등수를 구하라. 어떤 선수의 최선의 등수는 그 선수보다 앞에 있으면서 평소 실력이 더 좋은 선수의 수에 1을 더한 값이다.
입력
첫째 줄에 선수의 수를 나타내는 정수 N이 주어진다. N은 3 이상 500,000 이하이다.
다음 N개의 줄에는 각 선수의 평소 실력이 현재 앞에서 달리고 있는 선수부터 차례대로 하나씩 주어진다. 각 실력 값은 1 이상 1,000,000,000 이하의 정수이며, 모든 선수의 실력 값은 서로 다르다.
출력
입력에 주어진 선수 순서와 같은 순서로, 각 선수가 얻을 수 있는 최선의 등수를 한 줄에 하나씩 출력한다.