Longest Increasing Subsequence After Removal

Given an integer array \(nums\) of length \(n\), your task is to find the length of the longest strictly increasing subsequence that can be obtained after removing exactly one element from the array.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Note that the removal of an element is mandatory even if the array is already strictly increasing.

The problem can be approached by first computing the longest increasing subsequence (LIS) ending at each index and the longest increasing subsequence starting at each index. Then, by considering the effect of removing an element, you can potentially join two increasing sequences provided that the adjacent elements satisfy the increasing order condition \(nums[i-1] < nums[i+1]\).

Note: Although the ideal constraints for this problem might allow for more efficient solutions, for the purpose of this challenge you may assume a smaller input size (e.g. \(n \leq 10^5\)) so that an \(O(n^2)\) solution is acceptable.

inputFormat

The first line of input contains an integer \(n\) which represents the number of elements in the array. The second line contains \(n\) space-separated integers denoting the elements of the array \(nums\).

outputFormat

Output a single integer representing the length of the longest strictly increasing subsequence that can be obtained after removing exactly one element from the array.

## sample

6
5 3 4 8 6 7

4

</p>