Longest Increasing Subsequence after One Reversal

Farmer John is lining up his N cows (1 ≤ N ≤ 50) for a photograph. The height of the ith cow in the lineup is denoted by \(a(i)\). A subsequence of the array \(a(1), a(2), \dots, a(N)\) is any sequence \(a(i_1), a(i_2), \dots, a(i_k)\) with \(1 \le i_1 < i_2 < \cdots < i_k \le N\). We say that a subsequence is increasing if

[ a(i_1) \le a(i_2) \le \cdots \le a(i_k). ]

To help improve the aesthetics of his photo, Farmer John is allowed to take one action before taking the photograph. He may choose an arbitrary subsequence (not necessarily contiguous) of the cows and reverse its elements, leaving all other cows in their original positions. For example, if the cow heights are:

1 6 2 3 4 3 5 3 4

and we reverse the elements at positions 2, 7, and 8 (the marked positions below):

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

we obtain:

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

Your task is to determine the maximum possible length of an increasing subsequence that can be obtained after performing at most one such reversal operation.

Note: Reversal is optional — you may decide not to perform any reversal if it does not help.

inputFormat

The first line contains a single integer \(N\) (1 ≤ N ≤ 50). The second line contains \(N\) space‐separated integers \(a(1), a(2), \dots, a(N)\) representing the heights of the cows.

outputFormat

Output a single integer — the maximum possible length of an increasing (i.e. non‐decreasing) subsequence that can be achieved after at most one reversal operation on an arbitrary subsequence.

sample

9
1 6 2 3 4 3 5 3 4

7