Game of Rounding

Jack은 "Rounding"이라는 새 비디오 게임을 얻었다. 이 게임에는 $n$개의 레벨이 있다. 게임에는 전 세계 플레이어를 점수 순으로 줄 세우는 전역 랭킹 시스템이 있다. Jack은 세계 기록을 깨고 자신이 이 게임의 최고수임을 알리고 싶어서 점수 체계를 꼼꼼히 조사했다.

마침내 점수 규칙을 파악했다. 플레이어는 레벨을 하나 끝낼 때마다 점수를 얻는다. 플레이어의 점수는 레벨당 평균 점수를 가장 가까운 정수로 반올림한 값이다. 정확히는 플레이어가 $k$개의 레벨을 플레이해서 $p_1, p_2, \dots, p_k$점을 얻었다면, 점수는 $\left\lfloor \frac{\sum_{i=1}^k{p_i}}{k} + 0.5\right\rfloor$이다. 예를 들어 3개의 레벨에서 $[2, 3, 3]$점을 얻었다면 점수는 $\left\lfloor \frac{2+3+3}{3} + 0.5\right\rfloor = 3$이다.

Jack은 여러 번 연습해 봤고, 각 레벨 $i$에서 얻을 점수 $a_i$를 알고 있다. 그는 앞부분 레벨을 건너뛰고 원하는 시점에 멈출 수 있는 허점을 발견했다. 따라서 Jack은 $1 \le l \le r \le n$을 만족하는 쌍 $(l, r)$을 고를 수 있고, 레벨 $l$부터 $r$까지만 플레이할 수 있다.

$1 \le l \le n$인 각 시작 레벨 $l$에 대해, Jack이 달성할 수 있는 최대 점수와 그 점수에 도달하기 위해 플레이해야 하는 레벨 수를 구하려 한다. 최대 점수를 주는 선택이 여럿이면 오래 플레이하면 건강에 해로우니 가장 작은 레벨 수를 답한다.

첫 줄에 테스트 케이스의 수 $t$가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄에는 레벨의 수 $n$이 주어지고, 둘째 줄에는 각 레벨에서 얻는 점수 $a_1, a_2, \dots, a_n$이 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄에 $n$개의 정수를 출력한다. $i$번째 수는 레벨 $i$부터 시작해서 최대 점수를 얻기 위해 Jack이 플레이해야 하는 레벨 수이다. 최대 점수를 달성하는 선택이 여럿이면 가장 작은 레벨 수를 출력한다.

$1 \le t \le 10^5$

$1 \le n \le 2 \times 10^5$

$0 \le a_i \le 10^9$ ($i \in \{1, 2, \dots, n\}$)

모든 테스트 케이스의 $n$의 합은 $2 \times 10^5$을 넘지 않는다.