Dãy số ~B = (b_1, b_2, \ldots, b_m)~ được gọi là dãy con của dãy số ~A = (a_1, a_2, \ldots, a_n)~ khi và chỉ khi có thể tạo ra dãy ~B~ bằng cách xóa đi một số phần tử từ dãy ~A~ và giữ nguyên các phần tử còn lại để tạo ra dãy ~B~. Nói cách khác, tồn tại một bộ chỉ số ~i_1, i_2, \ldots, i_m~ sao cho ~1 \leq i_1 < i_2 < \ldots < i_m \leq n~ và ~b_j = a_{i_j}~ với mọi ~1 \leq j \leq m~.

Dãy con tăng dài nhất của một dãy số là dãy con dài nhất thỏa mãn tính chất: mọi phần tử đứng sau đều lớn hơn hẳn các phần tử đứng trước nó.

Cho dãy số ~A = (a_1, a_2, \ldots, a_n)~, bạn được phép đổi dấu (nhân với ~-1~) một dãy con liên tiếp của dãy ~A~. Nói cách khác, bạn được chọn hai chỉ số ~l~ và ~r~ sao cho ~1 \leq l \leq r \leq n~ và biến đổi dãy ban đầu thành ~a_1, a_2, \ldots, a_{l-1}, -a_l, -a_{l+1}, \ldots, -a_{r}, a_{r+1}, a_{r+2}, \ldots, a_n~. Bạn có thể không thực hiện phép biến đổi này nếu không muốn. Hãy biến đổi sao cho độ dài của dãy con tăng dài nhất sau khi biến đổi là lớn nhất.

Input

Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 220797)~. Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(0 \leq |a_i| \leq 10^9)~.

Output

Gồm một số nguyên duy nhất là độ dài lớn nhất của dãy con tăng dài nhất của dãy ~A~ sau khi biến đổi.

Giới hạn

• Subtask ~1~ (~27~ điểm): ~n \leq 10~
• Subtask ~2~ (~41~ điểm): ~n \leq 2207~
• Subtask ~3~ (~32~ điểm): ~n \leq 220797~

Sample Input 1

7
2 2 7 1 9 9 7

Sample Output 1

4

Sample Input 2

9
1 2 3 -4 -5 -6 7 8 9

Sample Output 2

9

Sample Input 3

9
1 2 3 4 5 6 7 8 9

Sample Output 3

9

Sample Input 4

9
9 8 7 6 5 4 3 2 1

Sample Output 4

9

Note

Trong ví dụ thứ nhất, ta biến đổi dãy thành ~(-2, 2, 7, 1, 9, 9, 7)~ để được dãy con tăng dài nhất là ~(-2, 2, 7, 9)~.

Trong hai ví dụ tiếp theo, ta biến đổi dãy thành ~(1, 2, 3, 4, 5, 6, 7, 8, 9)~.

Trong ví dụ thứ tư, ta biến đổi dãy thành ~(-9, -8, -7, -6, -5, -4, -3, -2, -1)~.