Difference Maximization

카이스트의 PS 동아리인 RUN은 무려 $N$명의 회원을 가지고 있는 유서깊은 동아리이다. 회원 수가 많은 만큼, RUN에는 매우 다양한 실력대의 회원들이 있다. RUN의 친목부장인 코코아는 회원들간의 친밀도를 조사하기 위해 회원들의 실력을 조사해두었다. 코코아는 $i$번째 회원의 실력이 양의 정수 $a_i$라는 사실과, 모든 회원들의 실력이 $M$ 이하라는 사실을 확인하였다.

코코아는 실력의 분포가 다양할수록 회원들간의 친밀도가 높을 것이라고 생각했다. 따라서, 코코아는 RUN의 친밀도를 $\sum_{1\le i<j\le n} |a_i-a_j|$와 같이 정의했다.

유감스럽게도, 업무를 처리하던 코코아는 회원들의 실력이 적힌 명부에 코코아를 쏟아 일부 회원들의 실력을 알아볼 수 없게 되었다! 코코아가 쏟아진 명부를 보면서, 문득 코코아는 알아볼 수 없게 된 회원들의 실력에 따른 RUN의 친밀도의 최댓값이 궁금해졌다. 코코아를 대신해서 실력을 알아볼 수 없는 회원들의 실력들을 $1$부터 $M$ 사이의 정수로 적절히 대체할 때, 가능한 RUN의 친밀도의 최댓값을 구해보자.

첫 줄에 RUN의 회원수인 정수 $N$과, 회원들의 실력의 상계인 정수 $M$이 주어진다.

그 뒤, 두 번째 줄에 $N$개의 음이 아닌 정수 $a_i$가 공백으로 구분되어 주어진다. 이는 $a_i\ge 1$이라면 $i$번째 회원의 실력이 $a_i$라는 것이고, $a_i=0$이라면 $i$번째 회원의 실력을 알아볼 수 없다는 것이다.

하나의 정수를 출력한다. 이는 $a_i=0$인 각 $i$들에 대해 해당 회원의 실력을 $1$부터 $M$사이의 정수로 적절히 대체하였을 때 얻을 수 있는 RUN의 친밀도의 최댓값이어야 한다.

• $1\le N\le 100\,000$
• $1\le M\le 10^6$
• 모든 $1 \le i \le N$에 대하여 $0\le a_i\le M$

RUN에는 친목부장이라는 임원직이 실존하지 않습니다. 만약 자신을 친목부장으로 자처하는 사람을 만난다면, 즉시 다른 임원진을 호출하세요.