Сізге ұзындығы $n$ болатын бір $p$ орын ауыстыруы берілген. $p$ орын ауыстыруының үзіліссіз ішкі кесіндісі үшін оның құнын осы ішкі кесіндінің ең ұзын өспелі ішкі тізбегінің ұзындығы ретінде анықтайық. $p$ орын ауыстыруын қиылыспайтын ішкі кесінділерге бөліктеу үшін оның құнын осы ішкі кесінділердің құндарының қосындысы ретінде анықтайық.

$p$ орын ауыстыруын $k$ бос емес қиылыспайтын ішкі кесіндіге бөліктеулердің ішіндегі ең үлкен құнды $a_k$ деп белгілейік.

Сізге $1$-ден $n$-ге дейінгі әрбір $k$ үшін $a_k$ мәнін табу қажет.

Кіріс деректер

Кіріс деректер бірнеше тест жағдайынан тұрады. Бірінші жолда бір бүтін сан $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$ екенін байқау оңай.