問題はこちら。

ある山小屋から見える山小屋の数は右手に見える山小屋の数と左手に見える山小屋の数の和だからそれぞれ計算する。計算にはヒープが使える。

import sys
from heapq import heappop, heappush
readline = sys.stdin.readline
INF = float('inf')


def main():
 N = int(readline())
 H = [INF] + [int(readline()) for _ in range(N)] + [INF]
 
 hq, l = [], [0] * (N + 2)
 for i, h in reversed(list(enumerate(H))):
   while len(hq) > 0 and hq[0][0] < h:
     k, j = heappop(hq)
     l[j] = j - i - 1
   heappush(hq, (h, i))
 hq, r = [], [0] * (N + 2)
 for i, h in enumerate(H):
   while len(hq) > 0 and hq[0][0] < h:
     k, j = heappop(hq)
     r[j] = i - j - 1
   heappush(hq, (h, i))
 ans = [l[i] + r[i] for i in range(1, N + 1)]
 print(*ans, sep='\n')


if __name__ == "__main__":
 main()