题目背景

一年一度的奉心祭到了，会长终于下定决心向辉夜表达自己的心意，这次，他的计划是心形气球。

题目描述

会长有很多心形气球，除去扎成一簇用于放飞的气球以外，还剩下 $n$ 个气球，每个气球有一个充气后的体积 $v_i$，这些气球用线串成一排，会长希望从中挑选一些作为场景布置。

然而，由于时间紧迫，他不能任意地挑选气球，因为剪断气球间的连线需要一定时间，于是他计划使用连续的一段气球。此外，为了美观，他不希望这一段气球中体积最大的或体积最小的被放在两端。

现在，他会优先考虑两端的气球选择哪一个。因此，你需要帮助他分别求出，对于每一个气球，将其作为左端和右端时，能够满足他要求的布置方案的数目。

形式化题意：给定序列 $\{v_n\}$，定义一个区间 $[l,r]$ 是“均衡区间”当且仅当 $\min\{v_l,v_r\} \ne \min \limits_{l\le i\le r}v_i$ 且 $\max\{v_l,v_r\} \ne \max \limits_{l\le i\le r}v_i$，你需要对所有的 $i(1\le i\le n)$ 分别求出以 $i$ 为左端点和右端点的均衡区间的个数。

输入格式

第一行两个整数 $n,id$，表示序列长度和测试点所属子任务的编号（样例中 $id=0$）。

第二行 $n$ 个整数，第 $i$ 个整数表示 $v_i$ 的值。

输出格式

输出共两行，每行 $n$ 个整数，第一行的第 $i$ 个整数表示以 $i$ 为左端点的方案数，第二行的第 $i$ 个整数表示以 $i$ 为右端点的方案数。

输入输出样例 #1

5 0
3 2 1 5 4

1 1 0 0 0
0 0 0 0 2

输入输出样例 #2

9 0
2 1 4 3 2 1 4 3 2

4 0 0 2 2 0 0 0 0
0 0 0 1 1 0 0 3 3

说明/提示

【本题采用捆绑测试】

• $\text{Subtask 1(10pts)}:id=1$，$n\le 200$。
• $\text{Subtask 2(5pts)}:id=2$，存在 $1\le i\le n$，使得 $v_1 \le v_2 \le \dots \le v_i$ 且 $v_i \ge \dots \ge v_{n-1} \ge v_n$。
• $\text{Subtask 3(15pts)}:id=3$，$n\le 5000$。
• $\text{Subtask 4(35pts)}:id=4$，$n\le 10^5$，。
• $\text{Subtask 5(35pts)}:id=5$，无特殊限制。

对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le v_i \le 10^9$空间限制为 256MB。