3851: Beauty Of Unimodal Sequence
内存限制：128 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
You are given an array of n integers a1,a2,...,an. We define that a sequence p1,p2,...,pk(k∈[1,n]) is beautiful if and only if these conditions are met:
∙ 1≤p1<p2<⋯<pk≤n.
∙ There exists t(t∈[1,k]) satisfying ap1<ap2<⋯<apt and apt>apt+1>⋯>apk.
You need to find all the longest beautiful sequences, and output the lexicographically smallest one and the lexicographically largest one in them.
Check the examples below for better understanding.
∙ 1≤p1<p2<⋯<pk≤n.
∙ There exists t(t∈[1,k]) satisfying ap1<ap2<⋯<apt and apt>apt+1>⋯>apk.
You need to find all the longest beautiful sequences, and output the lexicographically smallest one and the lexicographically largest one in them.
Check the examples below for better understanding.
输入
There are multiple test cases.
Each case starts with a line containing a positive integer n(n≤3×1e5).
The second line contains n integers a1,a2,...,an(1≤ai≤1e9).
It is guaranteed that the sum of Ns in all test cases is no larger than 1e6.
Each case starts with a line containing a positive integer n(n≤3×1e5).
The second line contains n integers a1,a2,...,an(1≤ai≤1e9).
It is guaranteed that the sum of Ns in all test cases is no larger than 1e6.
输出
For each test case, output two lines, the first of which depicts the lexicographically smallest one in longest beautiful sequences and the second of which depicts the lexicographically largest one in longest beautiful sequences.
样例输入 复制
7
1 4 2 5 7 4 6
3
1 2 3
3
3 2 1样例输出 复制
1 2 4 5 6
1 3 4 5 7
1 2 3
1 2 3
1 2 3
1 2 3