T3 均衡区间

题目信息

时间限制: 1s

空间限制: 256M

输入文件: interval.in

输出文件: interval.out

题目描述

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

输入格式

第一行两个整数 $n,id$，表示序列长度和测试点类型（样例中 $id=0$）。

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

输出格式

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

样例

样例输入 #1

5 0
3 2 1 5 4

样例输出 #1

1 1 0 0 0
0 0 0 0 2

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le n\le 10^6$，$1\le a_i \le 10^9$。

特殊性质：存在 $1\le i\le n$，使得 $a_1 \le a_2 \le \dots \le a_i$ 且 $a_i \ge \dots \ge a_{n-1} \ge a_n$。