题解

题目描述

给定一个由n个正整数构成的数组，我们可以删除恰好一个元素，求删除后数组中前缀最大值的最大数量。前缀最大值定义为：某个元素之前的所有元素都比它小。

思路分析

1. 前缀最大值预处理：首先计算原数组中每个位置的前缀最大值数量和当前最大值，以便快速获取删除某个元素后的前缀部分信息。
2. 后缀递增子序列预处理：从右到左预处理每个位置的最长递增子序列（LIS）长度，用于快速获取删除元素后剩余数组的递增序列长度。
3. 组合求解：对于每个可能的删除位置，计算前缀部分的数量和剩余部分能形成的最长递增子序列长度之和，取最大值作为答案。

题目内容

给定一个由n个正整数构成的数组{$a_1,a_2,....,a_n$}。

如果$a$中的任意一个元素$a_j(1≤j≤n)$,其对于所有的$(1≤i≤j-1)$，都有$a_i<a_j$，则我们称$a_j$为前缀最大值。

现在，你可以从数组中删除恰好一个元素,请问你能够得到的前缀最大值的最大数量是多少?

输入描述

第一行包含一个整数$n(1≤n≤10^5)$代表数组中的元素数量。

接下来一行包含$n$个正整数$a_1,a_2,...,a_n(1≤a_i≤10^9)$,表示数组$a$中的元素。

输出描述

在一行上输出一个整数，代表能够获得的前缀最大值的最大数量

样例1

输入

5
8 3 5 7 6

输出

3

说明

在给定的样例中，我们可以删除数组$a$中的第一个元素$i$得到{$3,5,7,6$}。此时$3,5,7$均为前缀最大值.