يُسمّى تسلسل من $n$ أعداد صحيحة $a_1,a_2,\ldots,a_n$ تبديلًا بحجم $n$ إذا ظهرت فيه جميع القيم من $1$ إلى $n$ مرة واحدة بالضبط.

يكون التسلسل $b_1,b_2,\ldots,b_l$ تسلسلًا جزئيًا من التسلسل $a_1,a_2,\ldots,a_n$ إذا أمكن الحصول على $b$ من $a$ بحذف بعض العناصر (أي إن $l\le n$ وتوجد فهارس $i_1<i_2<\ldots<i_l$ بحيث $a_{i_t}=b_t$).

• يُسمّى عنصر التسلسل $a_i$ رقمًا قياسيًا إذا كان أكبر تمامًا من جميع العناصر السابقة (أي $a_j<a_i$ لكل $1\le j<i$).
• يُسمّى عنصر التسلسل $a_i$ رقمًا قياسيًا أدنى إذا كان أصغر تمامًا من جميع العناصر السابقة (أي $a_j>a_i$ لكل $1\le j<i$).

لديك تبديل $p_1,p_2,\ldots,p_n$ بحجم $n$. المطلوب تقسيمه إلى تسلسلين جزئيين غير فارغين $q$ و$r$. بعبارة أخرى، يجب أن ينتمي كل عنصر من $p$ إلى واحد فقط من التسلسلين الجزئيين. ويجب تعظيم مجموع عدد الأرقام القياسية في $q$ وعدد الأرقام القياسية الدنيا في $r$.

الإدخال

يتكوّن كل اختبار من عدة حالات اختبار. يحتوي السطر الأول على عدد صحيح واحد $t$ ($1\le t\le100\,000$)، وهو عدد حالات الاختبار. تحتوي الأسطر $2t$ التالية على وصف حالات الاختبار.

يحتوي السطر الأول من وصف كل حالة اختبار على عدد صحيح واحد $n$، وهو حجم التبديل ($2\le n\le200\,000$).

يحتوي السطر الثاني من وصف كل حالة اختبار على $n$ أعداد صحيحة $p_1,p_2,\ldots,p_n$، وهي التبديل الأصلي. يُضمن أن كل عدد من $1$ إلى $n$ يظهر مرة واحدة بالضبط بين عناصر $p$.

لا يتجاوز مجموع $n$ على جميع حالات الاختبار $200\,000$.

الإخراج

لكل حالة اختبار، اطبع عددًا صحيحًا واحدًا: أكبر مجموع ممكن لعدد الأرقام القياسية في $q$ والأرقام القياسية الدنيا في $r$ عند اختيار التقسيم الأمثل.

المهام الفرعية

لنرمز بـ$N$ إلى مجموع قيم $n$ في جميع حالات الاختبار ضمن اختبار واحد.

أمثلة

الإدخال 1

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

الإخراج 1

5
6
3
5

ملاحظة

إحدى طرق تقسيم $p$ إلى $q$ و$r$ بشكل أمثل في حالة الاختبار الأولى هي كما يلي (الأرقام القياسية في $q$ والأرقام القياسية الدنيا في $r$ محاطة بإطارات):

• $q=\boxed{1}\ \boxed{2}\ \boxed{3}\ \boxed{5}$
• $r=\boxed{4}$

إحدى طرق تقسيم $p$ إلى $q$ و$r$ بشكل أمثل في حالة الاختبار الثانية هي كما يلي:

• $q=\boxed{3}\ \boxed{8}\ 4\ 1\ 2\ \boxed{9}$
• $r=\boxed{10}\ \boxed{7}\ \boxed{5}\ 6$