Sau những giờ training căng thẳng để chuẩn bị cho kỳ thi Olympic 30/4, nhằm cho các bạn ITK21 thư giãn đầu óc thì thầy Như đã nghĩ ra vài câu đố vui đơn giản mà trí tuệ.

Thầy đặt lên bàn một dãy liên tiếp \(n\) tấm thẻ, mỗi tấm chứa một số nguyên dương phân biệt từ \(1\) đến \(n\), nhưng các số này ban đầu không được sắp xếp theo một trật tự nào cả. Thầy quy ước vị trí hoàn hảo là vị trí thứ \(i\)_th bất kỳ (tính từ trái qua phải) sao cho số ở tại vị trí đó cũng đúng bằng \(i\). Dãy ban đầu có một số vị trí là hoàn hảo, cũng có một số vị trí không hoàn hảo.

Thầy cho phép các bạn chọn ra một đoạn con \(S\) bất kỳ gồm các phần tử liên tiếp trong dãy ban đầu \((1\leq |S|\leq n)\) sau đó xoay dãy con đó một góc \(180^{\circ}\). Hay nói cách khác là đổi chỗ tấm thẻ đầu và tấm thẻ cuối, tấm thẻ thứ hai và tấm thẻ áp cuối,... trong đoạn \(S\). Hãy tìm cách chọn đoạn con \(S\) sao cho sau khi thực hiện phép xoay thì số lượng vị trí hoàn hảo trong cả dãy số là nhiều nhất có thể.

Vì các bạn ITK21 đã "hết nhiên liệu" sau loạt contest training nên không thể nghĩ ra cách chọn tối ưu. Hãy giúp các bạn ấy nhé!

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) - số lượng tấm thẻ;
• Dòng tiếp theo chứa \(n\) số nguyên dương phân biệt là giá trị của các tấm thẻ theo thứ tự ban đầu.

Output

• In ra một số nguyên duy nhất là số vị trí hoàn hảo lớn nhất có thể đạt được sau khi xoay 1 đoạn con liên tiếp của dãy ban đầu.

Ví dụ

Sample input 1

5 
1 4 3 2 5

Sample output 1

5

Note

Ta đoạn con \([2..4]\), khi đó dãy trở thành 1 2 3 4 5, có \(5\) vị trí hoàn hảo.

Sample input 2

3 
1 2 3

Sample output 1

3

Note

Vì dãy ban đầu cả \(3\) vị trí đều đã hoàn hảo, nên ta chỉ cần chọn một đoạn con có kích thước \(1\) bất kỳ để xoay, nhằm đảm bảo số vị trí hoàn hảo không đổi. Giả sử ta chọn đoạn \([1..1]\), lúc đó dãy vẫn là 1 2 3, có \(3\) vị trí hoàn hảo.

Ràng buộc

• Subtask 1 (30% test cases): \(N\leq500\);
• Subtask 2 (30% test cases): \(N\leq5000\);
• Subtask 3 (40% test cases): \(N\leq500000\);