Bessie 有一个数 \(x+0.5\) ，其中 \(x\) 是某个 \(0\) 到 \(N\) 之间的整数（ \(1\le N\le 2 \cdot 10^5\) ）。

Elsie 正试着猜这个数。她可以以如下形式对于某个 \(1\) 到 \(N\) 之间的整数提问：「 \(i\) 是大了还是小了？」如果 \(i\) 大于 \(x+0.5\) ，Bessie 会回答 "HI"，如果 \(i\) 小于 \(x+0.5\) 则回答 "LO"。

Elsie 想到了以下猜测 Bessie 的数的策略。在进行任何猜测之前，她创建了一个包含 \(N\) 个整数的序列，其中从 \(1\) 到 \(N\) 的每个数均恰好出现一次（换句话说，这个序列是长为 \(N\) 的一个排列）。然后她遍历这一列表，按列表中的数的顺序依次猜数。

然而，Elsie 会跳过所有不必要的猜测。也就是说，如果 Elsie 将要猜某个数 \(i\) ，而 Elsie 之前已经猜过了某个 \(j < i\) 并且 Bessie 回答 "HI"，Elsie 不会再猜 \(i\) ，而是继续猜序列中的下一个数。类似地，如果她将要猜某个数 \(i\) ，而她之前已经猜过了某个 \(j > i\) 并且 Bessie 回答 "LO"，Elsie 不会再猜 \(i\) ，而是继续猜序列中的下一个数。可以证明，使用这一策略，对于 Elsie 创建的任意序列，她都可以唯一确定 \(x\) 。

如果我们将所有 Bessie 回答的 "HI" 或 "LO" 拼接成一个字符串 \(S\) ，那么 Bessie 说 "HILO" 的次数为 \(S\) 等于 "HILO" 的长为 \(4\) 的子串数量。

Bessie 知道 Elsie 将要使用这一策略；此外，她还知道 Elsie 将要使用的排列。然而， Bessie 尚未决定选用哪个值 \(x\) 。

帮助 Bessie 对于每个值 \(x\) 求出她会说 "HILO" 的次数。

输入的第一行包含 \(N\) 。

第二行包含 Elsie 的长为 \(N\) 的排列。

对于从 \(0\) 到 \(N\) 的每一个 \(x\) ，输出一行，包含 Bessie 会说 HILO 的次数。

样例1解释

对于 \(x=0\) ，Bessie 会说 "HIHI"，总计零次 "HILO"。 对于 \(x=2\) ，Bessie 会说 "HILOLOHIHI"，总计一次 "HILO"。 对于 \(x=3\) ，Bessie 会说 "HILOLOHILO"，总计两次 "HILO"。

数据范围

• 测试点 1-4 满足 \(N \leq 5000\) 。
• 测试点 5-8 为均匀随机的排列。
• 测试点 9-20 没有额外限制。