Farmer John đang xếp \(N\) con bò thành một hàng để chụp ảnh (\(1 \leq N \leq 50\)). Chiều cao của con bò thứ \(i\) trong hàng là \(a(i)\), và Farmer John cho rằng bức ảnh sẽ đẹp mắt nếu hàng bò có một dãy con tăng dài xét theo chiều cao.

Nhắc lại, một dãy con là một tập \(a(i_1), a(i_2), \ldots, a(i_k)\) gồm các phần tử trong dãy bò, được chọn tại một dãy chỉ số \(i_1<i_2<\ldots<i_k\). Ta gọi dãy con là tăng nếu \(a(i_1) \leq a(i_2) \leq \ldots \leq a(i_k)\).

Farmer John muốn thứ tự đàn bò của mình chứa một dãy con tăng dài. Để đạt được điều này, ban đầu ông cho phép mình chọn một dãy con bất kỳ và đảo ngược thứ tự các phần tử của nó.

Chẳng hạn, giả sử ta có dãy:

1 6 2 3 4 3 5 3 4

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

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

để thu được:

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

Hãy chú ý rằng dãy con sau khi bị đảo vẫn sử dụng đúng các chỉ số mà nó chiếm giữ ban đầu, còn những phần tử khác không thay đổi.

Hãy tìm độ dài lớn nhất có thể của một dãy con tăng, khi bạn được chọn một dãy con bất kỳ và đảo ngược nó một lần.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). \(N\) dòng còn lại chứa \(a(1) \ldots a(N)\), mỗi giá trị là một số nguyên trong khoảng \(1 \ldots 50\).

Dữ liệu ra

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

Ví dụ

9
1
2
3
9
5
6
8
7
4

9

Nguồn

USACO 2017 January Contest, Platinum — Subsequence Reversal. Tác giả đề: Lewin Gan.

https://usaco.org/index.php?page=viewproblem2&cpid=698