题目描述

有$N$个整数，输出这$N$个整数的最长上升序列、最长下降序列、最长不上升序列和最长不下降序列。

输入格式

第一行，仅有一个数$N$。 $N<=700000$

第二行，有$N$个整数。 $-10^9<=每个数<=10^9$

输出格式

第一行，输出最长上升序列长度。

第二行，输出最长下降序列长度。

第三行，输出最长不上升序列长度。

第四行，输出最长不下降序列长度。

样例数据

input

10

1 3 0 8 6 2 3 1 4 2

output

4

4

4

4

数据规模与约定

数据生成由 zqc，heaonan，zhouhang 等人对拍而成

时间限制：$1 \text {s}$

空间限制：$256 \text {MB}$