U568760 均衡区间

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

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

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

对于 $ 100\% $ 的数据，保证 $ 1 \leq n \leq 10^6 $，$ 1 \leq a_i \leq 10^9 $。 $ id = 0,n = 10^6 $