Bảo Bay Bổng đang trong tiết học thể dục. Thầy giáo bảo cả lớp xếp thành một hàng ngang. Lớp học của Bảo Bay Bổng có ~n~ học sinh, khi xếp thành hàng ngang, các học sinh được đánh số từ ~1~ tới ~n~ theo thứ tự từ trái qua phải. Học sinh thứ ~i~ có chiều cao ~h_i~.

Hai học sinh ~i~ và ~j~ có thể nhìn thấy nhau nếu như ở giữa họ không có học sinh nào có chiều cao lớn hơn. Cụ thể hơn, học sinh ~i~ và ~j~ ~(i < j)~ nhìn thấy nhau nếu như ~h_k \le h_i~ và ~h_k \le h_j~ với mọi ~k~ thỏa mãn ~i < k < j~.

Bảo Bay Bổng muốn biết với mỗi học sinh, người đó có thể nhìn thấy bao nhiêu học sinh khác mà có cùng chiều cao với họ.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~q~ ~(1 \le q \le 10)~ — số truy vấn.

• Mỗi truy vấn gồm hai dòng, dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~h_1, h_2, \ldots, h_n~ ~(1 \le h_i \le 10^9)~.

Kết quả

• Với mỗi truy vấn, in ra trên một dòng ~n~ số nguyên cách nhau bởi dấu cách là câu trả lời cho truy vấn đó.

Ví dụ

Sample Input

1
5
1 2 2 3 2

Sample Output

0 1 1 0 0

Giải thích

• Học sinh thứ ~2~ có thể nhìn thấy học sinh ~1, 3~ và ~4~ nhưng chỉ có học sinh ~3~ cùng chiều cao với học sinh ~2~.

• Học sinh thứ ~3~ chỉ nhìn thấy học sinh ~2~ là có cùng chiều cao bởi vì học sinh ~3~ không thể nhìn thấy học sinh ~5~ do có học sinh ~4~ có chiều cao lớn hơn.

Subtask

• Subtask 1 (~40\%~ số test): ~n \le 1000~.

• Subtask 2 (~60\%~ số test): Không có ràng buộc gì thêm.