تُعطى لك تبديلة واحدة $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$.