转化题意：如果回答 HI，那就找这个数之后第一个小于他的数，否则就找他之后第一个大于他的数。

考虑对原序列建笛卡尔树，且满足儿子的插入时间节点大于父亲，同时左儿子的值小于根小于右儿子，那么以插入时间为键值，每个数的值为下标构造笛卡尔树即可，这样题意就可以转化为在笛卡尔树上不断向左向右儿子走的过程。

我们现在有了一棵笛卡尔树，暴力遍历这棵树，如果是向左儿子走，说明回答的是 HI，否则就是 LO，再检查上一个是不是 HI，实时更新答案即可。

#include <bits/stdc++.h>
#define f(i ,m ,n ,x) for (int i = (m) ; i <= (n) ; i += (x))

template < typename T > inline void read ( T &x ) {
	x = 0 ;
	bool flag (0) ; char ch = getchar () ;
	while (! isdigit (ch)) {
		flag = ch == '-' ;
		ch = getchar () ;
	} while (isdigit (ch)) {
		x = (x << 1) + (x << 3) + (ch ^ 48) ;
		ch = getchar () ;
	} flag ? x = - x : 0 ;
} 

const int N = 2e5 + 7 ;
int n ,p[N] ,ls[N] ,rs[N] ,stk[N] ,stop ,a[N] ,ans[N] ;

inline void dfs (int cur ,int tot ,int las) {
	if (ls[cur]) dfs (ls[cur] ,tot ,1) ;
	if (rs[cur]) dfs (rs[cur] ,tot + (las == 1) ,0) ;
	if (! ls[cur]) ans[cur - 1] = tot ;
	if (! rs[cur]) ans[cur] = tot + (las == 1) ; 
}

int main () {
	read (n) ;
	f (i ,1 ,n ,1) read (p[i]) ,a[p[i]] = i ;
	int st = p[1] ;
	std :: sort (p + 1 ,p + n + 1) ;
	f (i ,1 ,n ,1) {
		if (! stop) stk[++ stop] = p[i] ;
		else {
			int cur = stop ;
			while (stop && a[stk[stop]] > a[i]) stop -- ;
			if (stop) rs[stk[stop]] = p[i] ;
			if (stop != cur) ls[p[i]] = stk[stop + 1] ;
			stk[++ stop] = p[i] ;  
		}
	}
	dfs (st ,0 ,0) ;
	puts ("0") ;
	f (i ,1 ,n ,1) std :: cout << ans[i] << '\n' ;
	return 0 ;
}