Cho một dãy chỉ gồm các phần tử 1 và 2. Bạn có thể thực hiện tối đa một thao tác đảo ngược đoạn [l , r] trong dãy để thu được dãy con không giảm dài nhất( không cần thiếp phải lien tiếp.)
Input : Dòng 1 chứa số nguyên dương n duy nhất là chiều dài của dãy (n <= 2 * 10^5).
Dòng 2 chứa n số nguyên a[i] chỉ gồm 1 và 2.
Output: In ra chiều dài dãy không giảm tối đa của dãy mới.
Examples:
|
Daycon.inp |
Daycon.out |
|
4 1 2 1 2 |
4 |
|
10 1 1 2 2 2 1 1 2 2 1 |
9 |
*Trong ví dụ 1 đảo đoạn [2,3] thu được dãy mới : 1 1 2 2.