题目描述

Alice 和 Bob 在玩猜数字游戏。 Alice 有一个小数 y，y 可以用 y=x+0.5 表示，其中 x 是一个 0 到 N 的整数。Bob 去猜这个数字。 Bob 会取 1 到 N 之间的一个整数 i 进行提问：i 是大还是小？但是 Alice 并不想说话，所以 Bob 准备了 两张选项卡 A 和 B，如果 i 大于 y，Alice 会选 A，如果 i 小于 y，Alice 会选 B。

Bob 的猜数字策略是：创建一个从 1 到 N 的排列（换句话说，创建一个包含 N 个整数的序列，其中 从 1 到 N 的每个数均恰好出现一次），然后他会按照数字出现的顺序依次猜数。同时，Bob 很聪明，他不 会枚举每一个数字，比如，Bob 接下来本来要拿出来猜的数是 i，而他之前已经猜过了某个数 j<i 并且 Alice 选择了 A，那么 Bob 就不会再猜 i，而是继续拿序列中的下一个数来猜，反之同理。可以证明，使用这一 策略，对于 Bob 创建的任一序列，他都可以成功猜到 x。

现在 Alice 还不知道用哪个 x 让 Bob 去猜，但是她知道 Bob 创建的排列是什么，我们把 Alice 回答的 A 或 B 拼接成一个字符串 s，请编程求出对于每一个 x（0<=x<=N），字符串 s 中子串“AB”出现了几次。

（详见样例）

输入格式

共 2 行：

第一行包含 N。

第二行包含一个长为 N 的排列，每个数之间用空格间隔。

输出格式

共 N+1 行：

对于从 0 到 N 的每一个 x，第 i 行，表示 Alice 选择 i-1 这个数字时回答串 s 中子串“AB”出现的 次数。

输入输出样例

输入 #1

5
5 1 2 4 3

输出 #1

0
1
1
2
1
0

说明/提示

【样例解释】

当 x=0 时，Alice 回答的字符串为“AA”，“AB”子串出现了 0 次。

当 x=2 时，Alice 回答的字符串为“ABBAA”，“AB”子串出现了 1 次。

当 x=3 时，Alice 回答的字符串为“ABBAB”，“AB”子串出现了 2 次。

【数据范围】

20%的数据： 1<=N<=5000。

另有 30%的数据：Bob 选择的序列为升序的排列。

100%的数据：1<=N<=2e5。