Weighted Alternating Subarray Removal

You are given an integer array A of size N.

Alternating Array Definition:

An array is called alternating if the difference between consecutive elements alternates between:

• positive

• negative

• positive

• negative (or the reverse pattern)

That means the sequence should go like:

• up, down, up, down... or

• down, up, down, up...

Task:

• You are allowed to remove exactly one continuous subarray from A

• After removal, the remaining left and right parts are joined together

• Return the maximum possible length of a valid alternating array that can be formed

📥 Input Format

• A single integer array A

📤 Output Format

• A single integer representing the maximum possible length of the resulting alternating array

⚙️ Constraints

• 2≤N≤1000002 \le N \le 1000002≤N≤100000

• −105≤A[i]≤105-10^5 \le A[i] \le 10^5−105≤A[i]≤105

🧪 Examples

Example 1

Input:

1 3 2 4 3

Output:

5

Explanation: The array is already alternating, so the maximum valid length remains 5.