멋진 전망

Shiny City는 아름다운 도시로, 세 가지로 유명하다. 길이 하나뿐이라는 점, 모든 건물의 높이가 서로 다르다는 점, 그리고 그 건물들 꼭대기에서 보이는 멋진 전망이다.

팬데믹이 시작된 뒤로 Shiny City를 찾는 관광객 수는 크게 줄었다. 당신은 멋진 블로그를 써서 관광객을 더 끌어들이고, 사랑스럽지만 몹시 비효율적인 이 도시가 재정적으로 파멸하는 것을 막기로 마음먹었다. 안타깝게도 블로그에는 아직 빠진 정보가 있다.

Shiny City에는 N개의 건물이 있고, i번째 건물은 위치 i로 식별된다. 건물 i에서 건물 j로 가는 데는 |i − j|분이 걸린다. 각 건물의 높이 Hi는 서로 다르고, 건물이 높을수록 꼭대기에서 보이는 전망이 좋다.

어떤 건물에 있을 때, 전망이 더 좋은 다른 건물로 가는 것이 가치 있을 수 있다. 이동 비용 때문에, 더 많은 시간을 들이지 않고 도달할 수 있는 더 높은 건물이 있다면 그 건물로 가는 것은 가치가 없다.

형식적으로, 건물 i에서 다른 건물 j로 가는 것은 |i − k| ≤ |i − j|이고 Hj < Hk인 k가 존재하지 않을 때 가치 있다고 한다. k는 i와 같을 수 있다.

당신은 블로그에 각 건물마다 그곳에서 가치 있는 다른 건물이 몇 개인지 쓰려고 한다. 이 정보를 모아야 한다. 그렇지 않으면 Shiny City는 영원히 파멸할 것이다.

첫 번째 줄에는 정수 N (1 ≤ N ≤ 105)이 주어지는데, 이는 Shiny City의 건물 수이다. 두 번째 줄에는 N개의 서로 다른 정수 H1, H2, . . . , HN (1 ≤ Hi ≤ 109, i = 1, 2, . . . , N)이 주어지는데, Hi는 건물 i의 높이이다.

한 줄에 N개의 정수를 출력한다. i번째 정수는 건물 i에서 가치 있는 건물의 수이다.