Longest Increasing Subsequence in a Circular Array

Given a circular array (A = [a_1, a_2, \ldots, a_n]), your task is to find the maximum length of an increasing subsequence (not necessarily contiguous) among all contiguous segments of the circular array. To be precise, if you "rotate" the array, you form segments of length (n) by taking elements from the end and beginning of the array. For each such segment, compute the length of the Longest Increasing Subsequence (LIS) and return the maximum value among all segments.

Note: The Longest Increasing Subsequence of an array is the longest sequence (a_{i_1}, a_{i_2}, \ldots, a_{i_k}) such that (a_{i_1} < a_{i_2} < \cdots < a_{i_k}) with (1 \le i_1 < i_2 < \cdots < i_k \le n).

inputFormat

Input is given via standard input. The first line contains a single integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array. If (n = 0), no further input follows and the output should be 0.

outputFormat

Output a single integer representing the maximum length of an increasing subsequence among all the contiguous segments of the circular array. The result is printed via standard output.## sample

6
2 3 1 5 4 6

4