תמורה בגודל $n$ היא סדרה של $n$ מספרים שלמים $a_1,a_2,\ldots,a_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$