상품
시간 제한1초메모리 제한512 MB
각 k(2 이상 n 이하)마다, 진행자가 상품 하나를 먼저 제거한 뒤 페티야가 고를 때 상품 1번부터 k번 중 반드시 얻을 수 있는 최대 가치를 구한다.
문제
페탸는 n개의 상품이 걸린 대회에 참가한다. 상품에는 1부터 n까지 번호가 붙어 있다.
대회 결과에 따라 참가자는 2점부터 n점까지 얻을 수 있다. 참가자가 k점을 얻으면 번호가 1부터 k인 상품 중 하나를 받는다. 참가자가 상품을 고르기 전에 진행자가 상품 목록에서 상품 하나를 지운다. 그런 다음 참가자는 남은 k - 1개의 상품 중 아무거나 고를 수 있다.
상품 목록을 알게 된 페탸는 각 상품의 가치를 정했다. i번째 상품의 가치는 정수 ai이다.
상품의 가치가 주어졌을 때, 2부터 n까지의 각 k에 대해 페탸가 대회에서 k점을 얻으면 어떤 최대 가치의 상품을 반드시 받게 되는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 n이 주어진다. (2 ≤ n ≤ 100 000) 둘째 줄에는 n개의 정수 a1, a2, …, an이 주어진다. (1 ≤ ai ≤ 10^9)
출력
2부터 n까지의 각 k에 대해 페탸가 k점을 얻었을 때 받게 되는 상품의 가치를 나타내는 n - 1개의 정수를 한 줄에 출력한다.