Farmer John xếp $N$ bò thành hàng để chụp ảnh ($1 \leq N \leq 50$). Chiều cao con thứ $i$ là $a(i)$. Ông thấy ảnh đẹp nếu có dãy con tăng theo chiều cao dài.

Dãy con gồm $a(i_1), a(i_2), \ldots, a(i_k)$ tại chỉ số $i_1 < i_2 < \ldots < i_k$. Nó tăng nếu $a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)$.

Để có dãy con tăng dài, ban đầu ông có thể chọn dãy con bất kỳ và đảo thứ tự các phần tử.

Ví dụ với dãy

1 6 2 3 4 3 5 3 4

có thể đảo các phần tử được chọn

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

để được

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

Dãy con bị đảo vẫn dùng các chỉ số cũ, còn phần tử khác không đổi.

Tìm độ dài lớn nhất của dãy con tăng khi có thể đảo dãy con bất kỳ một lần.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa $N$. $N$ dòng còn lại chứa $a(1) \ldots a(N)$, mỗi số nguyên trong $1 \ldots 50$.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

In số phần tử của dãy con tăng dài nhất có thể sau khi đảo nhiều nhất một dãy con.

Ví dụ

Dữ liệu vào 1

9
1
2
3
9
5
6
8
7
4

Dữ liệu ra 1

9

Tác giả bài toán: Lewin Gan