타잔 점프

알마티 근처의 숲에 나무 $N$그루가 한 줄로 서 있다. 나무는 왼쪽부터 오른쪽으로 1번부터 $N$번까지 번호가 붙어 있다. $i$번 나무의 높이는 $H_i$이다.

한 번의 점프에서 타잔은 $i$번 나무의 꼭대기에서 $j$번 나무($i < j$)의 꼭대기로 이동할 수 있다. 이는 다음 조건 중 하나 이상이 성립할 때이다.

• $j = i + 1$,
• 모든 $k$ ($i < k < j$)에 대해 $H_i > H_k$이고 $H_j > H_k$,
• 모든 $k$ ($i < k < j$)에 대해 $H_i < H_k$이고 $H_j < H_k$.

타잔은 1번 나무 위에 있고 $N$번 나무에 도달하려 한다. 타잔의 ICPC 팀원 아베이가 도울 수 있다. 아베이는 다음 변경을 원하는 만큼 몇 번이고 할 수 있다. 번호 $i$ ($1 \le i \le n$)와 정수 $x$ ($0 \le x \le 10^{18}$)를 고른 뒤 $H_i = x$로 설정한다.

$k$를 1부터 $N$까지 각각 두고, 타잔이 $k$번 이하의 점프로 $N$번 나무에 도달할 수 있도록 아베이가 해야 하는 변경 횟수의 최솟값을 구하라.

첫 줄에 테스트 케이스의 수 $t$가 주어진다 ($1 \le t \le 150\,000$). 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫 줄에는 나무의 수 $N$이 주어진다 ($2 \le N \le 300\,000$).

둘째 줄에는 $N$개의 정수 $H_1, H_2, \ldots, H_N$이 주어진다 ($1 \le H_i \le 10^9$).

모든 테스트 케이스의 $N$ 합은 $300\,000$을 넘지 않는다.

각 테스트 케이스마다 정수 $N$개를 출력한다. $k$번째 정수는 타잔이 1번 나무에서 $N$번 나무까지 $k$번 이하의 점프로 갈 수 있게 하려고 아베이가 해야 하는 변경 횟수의 최솟값이다.

첫 번째 테스트 케이스에서 $k = 1$일 때 아베이가 1번 나무의 높이를 3으로 바꾸면 타잔은 마지막 나무로 뛸 수 있다. $k = 2$와 $k = 3$일 때는 변경 없이 타잔이 마지막 나무에 도달할 수 있다.