보물 찾기

Morgan은 보물찾기 행사를 위해 보물 창고를 설계하고 있다. 보물 창고는 0번부터 $N + 1$번까지 번호가 붙은 1차원 격자이며, 칸은 모두 $N + 2$개이다. 각 칸은 비어 있거나 보물이 있다. 처음에 0번 칸과 $N + 1$번 칸에는 보물이 있고, 나머지 칸은 비어 있다.

Morgan은 설계를 실험하면서 1번부터 $Q$번까지 번호가 매겨진 $Q$번의 갱신을 한다. $i$번째 갱신에서 Morgan은 $A_i$번 칸을 바꾼다. 칸이 비어 있으면 보물을 놓고, 보물이 있으면 보물을 치워 칸을 비운다. 모든 $i$에 대해 $1 \le A_i \le N$이 보장되므로, 0번 칸과 $N + 1$번 칸에는 항상 보물이 있다.

각 갱신 후에 Morgan은 보물찾기가 얼마나 어려운지 알고 싶어 한다. $x$번 칸에 서 있을 때의 난이도는 두 값의 곱이다. 하나는 $x$에서 $y \le x$인 칸 중 가장 가까운 보물까지의 거리이고, 다른 하나는 $x$에서 $y \ge x$인 칸 중 가장 가까운 보물까지의 거리이다. 두 칸 사이의 거리는 번호 차이의 절댓값이다. 전체 난이도는 $0 \le x \le N + 1$인 모든 $x$번 칸의 난이도를 더한 값이다.

첫 줄에 두 정수 $N$과 $Q$가 주어진다 ($1 \le N \le 100000$; $1 \le Q \le 100000$). 이어지는 $Q$개의 줄에는 각각 $i$번째 갱신에서 바꿀 칸을 나타내는 정수 $A_i$ ($1 \le A_i \le N$)가 하나씩 주어진다.

각 갱신 후, 그 시점의 전체 난이도를 한 줄에 출력한다.