50005. Final Prob. 5: 貓咪健康檢查

I'm a slow walker, but I never walk backwards.

一年一度的貓咪健康檢查要開始囉!

這天有$N$隻可愛的貓咪要來接受Roger的健康檢查,他們排成一排並乖乖的面向前方,從前到後第$i$隻貓咪的高度為$H$i

貓咪是一種充滿好奇心的動物,因此他們想知道自己往前看可以看到幾隻貓咪的頭頂呢?

假設貓咪可以看到比他矮的貓咪的頭頂,且一旦遇到高度不小於自己的貓咪,目光便會被遮蔽無法通過。

Input format:

輸入的第一列有一個正整數$T$,代表接下來有$T$組測試資料。

對於每組測試資料的第一列有一個正整數$N$,代表有$N$隻貓咪要接受健康檢查。

第二列有$N$個正整數,依序代表從前到後這$N$隻貓咪的高度,分別為$H$1$, H$2$, ..., H$N

Output format:

輸出共$T$列,對於每一列請輸出$N$個數字,依序代表這$N$隻貓咪往前看可以看到幾隻貓咪的頭頂(以空格隔開)。

特別注意:

*由於Judge是嚴格比對的,所以每列的最末端請不要輸出多於空格。

*由於輸入、輸出規模較大,請使用較快的I/O方式。

數據範圍:

$1 \leq T \leq 10$
$1 \leq H_i \leq 10^9$
$1 \leq N \leq 10^6$

Subtask:

  1. (2 pts) Sample
  2. (2 pts) $N = 1$
  3. (2 pts) $N = 2$
  4. (2 pts) $N = 3$
  5. (2 pts) 全部貓咪的身高都一樣,即$H$1 $= H$2 $= ... = H$N
  6. (5 pts) $N \leq 1000$
  7. (10 pts) 無額外限制

Sample input:

10
1
1
2
1 2
2
2 1
3
1 2 3
3
1 3 2
3
2 1 3
3
2 3 1
3
3 1 2
3
3 2 1
5
1 1 1 1 1

Sample output:

0
0 1
0 0
0 1 2
0 1 0
0 0 2
0 1 0
0 0 1
0 0 0
0 0 0 0 0

Discussion