Longhoang08 là một lập trình viên rất thích các vấn đề về dãy số. Anh ta quy định một dãy số là dãy số đẹp nếu nó đồng thời thỏa mãn các điều kiện sau:

   - Độ dài của dãy số đó là một số chẵn.

   - Giả sử dãy số đó gồm 2 * k phần tử b1, b2, ..., b2k thì bi < bi + k với mọi i, 1 <= i <= k.

Longhoang08 có một dãy số gồm n phần tử a1, a2, ..., an. Anh ta muốn tìm một dãy con (không nhất thiết phải liên tiếp) của dãy số này sao cho dãy con đó là một dãy số đẹp. Longhoang08 muốn dãy con mình tìm được có độ dài lớn nhất có thể, nhưng anh ta chưa thể giải quyết được bài toán này vì số lượng số của dãy khá lớn. Bạn sẽ giúp longhoang08 chứ?

   - Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 500).

   - Dòng thứ hai chứa n số nguyên a1, a2, ..., an (1 ≤ |ai| ≤ 10⁹ với 

   - Ghi ra một số nguyên duy nhất là kết quả bài toán.

   - 20% số test ứng với 20% số điểm có 1 ≤ n ≤ 20.

   - 40% số test ứng với 40% số điểm có 1 ≤ n ≤ 100.

   - 40% số test còn lại không có giới hạn gì thêm.