Shift LIS

题号：NC237188
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given a sequence $a_1, a_2,..., a_n$ .

You can now perform zero to any number of operations, each of which can right shift the sequence.(if you right shift $p_1, p_2,....p_{n-1},p_n$ , you will get $p_n, p_1, p_2, ..., p_{n-1}$ ).

Maximize the length of the longest non-decreasing sequence of the sequence.

输入描述:


The first line contains an integer  - the length of the sequence.

The second line contains  integers -

输出描述:

Output an integer - the length of the longest non-decreasing sequence after some operations.

示例1

输入

复制

6
5 1 6 2 3 4

输出

复制

说明

In the test case, we can right shift 5 times.

[5,1,6,2,3,4] -> [4,5,1,6,2,3] -> [3,4,5,1,6,2] -> [2,3,4,5,1,6] -> [6,2,3,4,5,1] -> [1,6,2,3,4,5] 

the length of longest non-decreasing sequence equals to 5.