[LIS模板]114514个ztx(doge)
\(\textcolor{black}{\textup{\textrm{题目背景}}}\)
\(\textcolor{black}{\textup{\textrm{洛谷}}}\)\(\textcolor{black}{\textup{\textrm{题目传送门\_U400526}}}\)
\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{在Kun房玩游戏，把hqz坑惨了，导致hqz}}}\)
\(\textcolor{black}{\textup{\textrm{很}}}\)
\(\textcolor{black}{\textup{\textrm{生}}}\)
\(\textcolor{black}{\textup{\textrm{气}}}\)
\(\textcolor{black}{\textup{\textrm{hqz使用了一些小小的魔法，变出了homo个}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{，并把它们丢在hqz家的火炉上排成一列以永久惩罚（假设hqz家的火炉无限大）}}}\)
\(\textcolor{black}{\textup{\textrm{※免责声明※}}}\)
\(\textcolor{black}{\textup{\textrm{本体人物皆为虚拟，无任何恶意}}}\)
\(\textcolor{black}{\textup{\textrm{请注意}}}\)
\(\textcolor{black}{\textup{\textrm{此提示upt时间为2024/1/23\ 20:54:49，共10个数据点，后面可能会进行upt}}}\)
\(\textcolor{black}{\textup{\textrm{有关hack数据点的请注意}}}\)
\(\textcolor{black}{\textup{\textrm{这道题数据是我自己写了一个随机数程序生成数据的，且homo都保证其中存在正好满足数}}\\\textup{\textrm{据范围}}\\\textup{\textrm{你可以去hack，但这样只会浪费你的时间。众所周知，\ 时间就是金钱\ ，你浪费这么多钱，}}\\\textup{\textrm{去干一件\ \Large{毫无意义}}}\textup{\textrm{\ 的事情，你不觉得自己很\ Joker\ 吗???!!! 众所又周知，\ 时间就是生命\ ，}}\\\textup{\textrm{你说你家里有矿随便浪费钱就算了，你还要\ ******\ 干嘛???!!!}}}\)
\(\textcolor{black}{\textup{\textrm{题目描述}}}\)
\(\textcolor{black}{\textup{\textrm{有homo个}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{站成一排，它们有高有矮}}}\)
\(\textcolor{black}{\textup{\textrm{现在请求出这些}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{构成的\ 最长上升子序列\ (\ LIS\ )}}}\)
\(\textcolor{black}{\textup{\textrm{Black\ Box吃下去的格式}}}\)
\(\textcolor{black}{\textup{\textrm{第一行一个homo表示}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{的个数}}}\)
\(\textcolor{black}{\textup{\textrm{接下来homo行，每行“亿”个}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{_{\textup{\textrm i}}\textup{\textrm{ ，表示第i个}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{的身高}}}\)
\(\textcolor{black}{\textup{\textrm{Black\ Box拉出来的格式}}}\)
\(\textcolor{black}{\textup{\textrm{仅一个数表示}}}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{\textup{\textrm{构成的LIS长度}}}\)
\(\textcolor{black}{\textup{\textrm{题意翻译}}}\)
\(\textcolor{black}{\textup{\textrm{English :}}}\)
\(\textcolor{black}{\textup{\textrm{PLEASE\ TRANSLATE\ YOURSELF,\ }}}\)
\(\textcolor{black}{\textup{\textrm{MY\ DEAR\ BIG\ CLEVER!!!!!!}}}\)
\(\textcolor{black}{\textup{\textrm{输入输出样例}}}\)
\(\textcolor{black}{\textup{\textrm{输入样例\ \#1}}}\)
1
1
\(\textcolor{black}{\textup{\textrm{输出样例\ \#1}}}\)
1
\(\textcolor{black}{\textup{\textrm{输入样例\ \#2}}}\)
5
1
2
3
4
3
\(\textcolor{black}{\textup{\textrm{输出样例\ \#2}}}\)
4
\(\textcolor{black}{\textup{\textrm{输入样例\ \#3}}}\)
8
389
207
155
300
299
170
158
65
\(\textcolor{black}{\textup{\textrm{输出样例\ \#3}}}\)
2
\(\textcolor{black}{\textup{\textrm{输入样例\ \#4}}}\)
人，不可贪心矣。
既已有叁个测试点，为何还不知足矣???!!!
Translate into English:
You are toooooooooooo cupidity to see the 4th point!!!!!!
\(\textcolor{black}{\textup{\textrm{输出样例\ \#4}}}\)
人，不可贪心矣。
既已有叁个测试点，为何还不知足矣???!!!
Translate into English:
You are toooooooooooo cupidity to see the 4th point!!!!!!
\(\textcolor{black}{\textup{\textrm{说明/提示}}}\)
\(\textcolor{black}{\textup{\textrm{对于20\%的数据点，保证homo}}\le15，}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{_{\textup{\textrm i}}\le900。}\)
\(\textcolor{black}{\textup{\textrm{对于50\%的数据点，保证homo}}\le10000，}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{_{\textup{\textrm i}}\le114514。}\)
\(\textcolor{black}{\textup{\textrm{对于60\%的数据点，保证homo}}\le11451。}\)
\(\textcolor{black}{\textup{\textrm{对于所有数据点，保证\ \Large{数据点全为随机}}}\textup{\textrm{\ ，且1}}\le\textup{\textrm{homo}}\le100000，}\)\(\textcolor{black}{\textup{\textrm{ztx}}}\)\(\textcolor{black}{_{\textup{\textrm i}}\le\textup{\textrm{1919810 (请注意时间复杂度)。}}}\)
\(\textcolor{black}{\textup{\textrm{C++ 语言 cin/cout 输入/输出优化}}}\)
//这是C++ 语言 cin/cout 输入/输出优化
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
//这是C++ 语言 cin/cout 输入/输出优化
\(\textcolor{lightgray}{\textup{\textrm{P.\ S.\ :\ }}}\)\(\textcolor{lightgray}{\textup{\textrm{S\ H\ X }}}\)\(\textcolor{lightgray}{\textup{\textrm{A\ K }}}\)\(\textcolor{lightgray}{\textup{\textrm{I\ O\ I}}}\)
