Chỉ số tốt

Trong một buổi phỏng vấn với báo chí, FullHouse Dev đã chia sẻ về một bài toán thú vị mà họ gặp phải trong quá trình phát triển phần mềm. Đó là bài toán về việc tìm các chỉ số tốt trong một mảng số nguyên, nơi mà mỗi phần tử cần lớn hơn cả hai phần tử xung quanh nó.

Bài toán

FullHouse Dev được cung cấp một mảng \(A\) gồm \(n\) số nguyên. Họ có thể thực hiện thao tác sau trên mảng:

• Chọn một chỉ số \(i\) và xóa phần tử thứ \(i\) khỏi mảng \(A\).

Với mỗi vị trí \(i\) (từ \(1\) đến \(n\)), cần tìm số thao tác tối thiểu để phần tử tại vị trí \(i\) trở thành lớn hơn cả hai phần tử xung quanh. Nếu không thể thực hiện được, in ra \(-1\) cho vị trí đó.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu tiên của mỗi test case chứa số nguyên \(n\)
• Dòng thứ hai chứa \(n\) số nguyên - các phần tử của mảng \(A\)

OUTPUT FORMAT:

• Với mỗi test case, in ra \(n\) số nguyên, trong đó số thứ \(i\) biểu thị số thao tác tối thiểu cần thực hiện để vị trí \(i\) trở thành chỉ số tốt

Ràng buộc:

• \(1 \leq T \leq 100\)
• \(1 \leq n \leq 10^5\)
• Tổng của \(n\) trong tất cả các test case không vượt quá \(10^5\)

Ví dụ

INPUT

1
5
1 2 3 5 1

OUTPUT

-1 2 1 0 -1

Giải thích

Với test case đã cho, \(T = 1\), \(n = 5\) Mảng \(A = [1, 2, 3, 5, 1]\)

• Với \(i = 1\): Vì không có phần tử bên trái, nên kết quả là -1
• Với \(i = 2\): Cần xóa hai phần tử 3 và 5, mảng trở thành [1, 2, 1]. Khi đó 2 lớn hơn cả hai phần tử xung quanh. Vậy kết quả là 2
• Với \(i = 3\): Xóa phần tử 5, mảng trở thành [1, 2, 3, 1]. Kết quả là 1
• Với \(i = 4\): 5 đã lớn hơn cả hai phần tử xung quanh. Kết quả là 0
• Với \(i = 5\): Vì không có phần tử bên phải, nên kết quả là -1