נתונה לכם תמורה אחת $p$ באורך $n$. עבור תת-מקטע רציף של $p$, נגדיר את העלות שלו בתור האורך של תת-הסדרה העולה הארוכה ביותר של תת-מקטע זה. עבור חלוקה של $p$ לתת-מקטעים זרים, נגדיר את העלות שלה בתור סכום העלויות של תת-מקטעים אלה.

נגדיר את $a_k$ בתור העלות המקסימלית מבין כל החלוקות של $p$ ל-$k$ תת-מקטעים זרים לא-ריקים.

עליכם למצוא את $a_k$ עבור כל $k$ מ-$1$ עד $n$.

קלט

הקלט מכיל מספר מקרי בדיקה. השורה הראשונה מכילה מספר שלם יחיד $t$ ($1 \le t \le 10^3$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה מספר שלם $n$ ($1 \le n \le 10^5$).

השורה השנייה מכילה $n$ מספרים שלמים שונים $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). יחד, הם מגדירים תמורה של $1, 2, \dots, n$.

סכום ערכי ה-$n$ על פני כל מקרי הבדיקה אינו עולה על $10^5$.

פלט

עבור כל מקרה בדיקה, הדפיסו את $a_1, a_2, \dots, a_n$ בשורה אחת.

דוגמאות

קלט 1

5
5
1 2 3 4 5
5
5 4 3 2 1
8
2 4 1 3 6 5 8 7
9
3 2 1 6 5 4 9 8 7
1
1

פלט 1

5 5 5 5 5
1 2 3 4 5
4 6 7 8 8 8 8 8
3 4 5 6 7 8 9 9 9
1

הערה

נתבונן במקרה הבדיקה השלישי עם התמורה $p = [2, 4, 1, 3, 6, 5, 8, 7]$:

• עבור $k = 1$, התשובה היא פשוט האורך של תת-הסדרה העולה הארוכה ביותר ב-$p$, שהוא $a_1 = 4$.
• עבור $k = 2$, לחלוקה ל-$[2, 4]$ ו-$[1, 3, 6, 5, 8, 7]$ יש את העלות המקסימלית: $a_2 = 2 + 4 = 6$.
• עבור $k = 3$, לחלוקה ל-$[2, 4]$, $[1, 3, 6]$ ו-$[5, 8, 7]$ יש את העלות המקסימלית: $a_3 = 2 + 3 + 2 = 7$.
• עבור $k = 4$, לחלוקה ל-$[2, 4]$, $[1, 3, 6]$, $[5, 8]$ ו-$[7]$ יש את העלות המקסימלית: $a_4 = 2 + 3 + 2 + 1 = 8$.
• עבור $k > 4$, קל לראות ש-$a_k = 8$.