Farmer John מסדר $N$ פרות בשורה לתמונה ($1 \leq N \leq 50$). גובה הפרה ה־$i$ הוא $a(i)$, ותת־סדרה עולה ארוכה של גבהים תעשה את התמונה יפה.

תת־סדרה היא איברים $a(i_1), a(i_2), \ldots, a(i_k)$ באינדקסים $i_1 < i_2 < \ldots < i_k$. היא עולה אם $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

כדי לקבל תת־סדרה עולה ארוכה, הוא רשאי בתחילה לבחור תת־סדרה כלשהי ולהפוך את סדר איבריה.

למשל ברשימה

1 6 2 3 4 3 5 3 4

אפשר להפוך את האיברים הנבחרים

1 6 2 3 4 3 5 3 4
  ^         ^ ^ ^

ולקבל

1 4 2 3 4 3 3 5 6
  ^         ^ ^ ^

תת־הסדרה ההפוכה תופסת את אותם אינדקסים, ושאר האיברים אינם משתנים.

מצאו את האורך המרבי של תת־סדרה עולה כשמותר להפוך תת־סדרה שרירותית פעם אחת.

קלט

קראו מהקלט הסטנדרטי.

השורה הראשונה מכילה $N$. $N$ השורות האחרות מכילות $a(1) \ldots a(N)$, כל אחד שלם בטווח $1 \ldots 50$.

פלט

כתבו לפלט הסטנדרטי.

הדפיסו את מספר האיברים בתת־הסדרה העולה הארוכה ביותר האפשרית אחרי היפוך לכל היותר תת־סדרה אחת.

דוגמאות

קלט 1

9
1
2
3
9
5
6
8
7
4

פלט 1

9

מחבר הבעיה: Lewin Gan