히스토그램 하나 넣기

길이 $N$의 수열 $A=[A_1,A_2,\cdots,A_N]$과 정수 $x$가 주어진다.

각 $k=0,1,\cdots,N$에 대해, 수열 $A$의 $k$번째 위치 뒤에 $x$를 하나 삽입한 새로운 수열을 생각하자.

즉,

• $k=0$이면 $x$를 $A_1$ 앞에 삽입한다.
• $1 \le k \le N-1$이면 $A_k$와 $A_{k+1}$ 사이에 $x$를 삽입한다.
• $k=N$이면 $x$를 $A_N$ 뒤에 삽입한다.

이렇게 얻은 길이 $N+1$의 수열을 $B^{(k)}$라고 하자. 각 $k=0,1,\cdots,N$에 대해, 수열 $B^{(k)}$로 만든 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$N\ x$ $A_1\ A_2\ \ \cdots \ A_N$

총 $N+1$개의 줄을 출력한다.

$k+1$번째 줄에는 $B^{(k)}$로 만든 히스토그램에서 만들 수 있는 가장 큰 직사각형의 넓이를 출력한다.

• $1 \le N \le 200\,000$.
• $1 \le x \le 10^9$.
• $1 \le A_i \le 10^9$ $(1 \le i \le N)$.