#DP0009. 最长不增子序列强化版

最长不增子序列强化版

题目描述

给定一个长度为 nn 的数组 a1,a2,,ana_1,a_2,…,a_n,问其中的最长上升子序列的长度。也就是说,我们要找到最大的 mm 以及数组 p1,p2,,pmp_1 , p_2 , … , p_m ,满足 1p1<p2<<pmn1≤p_1<p_2<⋯<p_m≤n 并且 ap1ap2apma_{p_1}\geq a_{p_2}\geq⋯\geq a_{p_m}

输入格式

第一行一个数字 nn

接下来一行 nn 个整数 a1,a2,,ana_1,a_2,…,a_n

输出格式

一个数,表示答案。

Samples

6
3 7 4 4 8 4
4

数据规模

对于所有数据,保证 1n2×105,1ai1091≤n≤2\times10^5,1≤a_i≤10^9