说明

现有一个环，环上有 $n$ 个数，第 $i$ 个数是 $a_i$，其中第 $i(1 ≤ i < n)$ 个和第 $i + 1$ 个相邻，第 $n$个和第 $1$ 个相邻。

每次操作你可以做以下事情之一：

1. 选取 $i$，设 $l, r$ 分别为与 $i$ 左右相邻的数，将 $a_i$ 变为 $\min(a_i, a_l, a_r)$。

2. 选取 $i$，设 $l, r$ 分别为与 $i$ 左右相邻的数，将 $a_i$ 变为 $\max(a_i, a_l, a_r)$。

你需要对于每个 $k(1 ≤ k ≤ m)$ 求出：最少操作多少次，才能使得所有数都等于 $k$。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数，分别表示 $a_1$，$a_2$，$\cdots$，$a_n$。

输出格式

共一行 $m$ 个整数，第 $k$ 个表示最少操作多少次，使得所有数都等于 $k$，若无法做到，输出 $-1$。

样例

7 5
2 5 1 1 2 3 2

5 5 7 -1 6