ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Timus Top Coders: Second Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Queen

Time limit: 1.0 second
Memory limit: 64 MB


Years and years have passed since famous grand master Paul V. Pawnstein invented N-dimensional chess and formulated the classical problem "Queen II". Since then hundreds of researchers tried their best to cognize its inconceivable essence and get to the solution, but only few of them have finally succeeded. The others, as usual, began to whimper and complain of this problem's baffling complexity. "Give us something easier! Let it be not two moves, but only one, please?", - demanded those thoughtless comrades.
But the grand master foresaw it. He knew exactly, that a scalability of the limitations is a great thing. And as if he tried to scoff at the simplicity lovers, Mr. Pawnstein posed a problem which was known as "Queen I".


A board in N-dimensional chess is N-dimensional cube S*S*...*S cells in size. A cell in one of its corners (this corner is chosen at will) has coordinates (1, 1, ..., 1), and a cell in the opposite corner has coordinates (S, S, ..., S).
A rook in N-dimensional chess makes its move shifting by any non-zero number of cells along one of its coordinates. A bishop in N-dimensional chess makes its move shifting by any non-zero number of cells along all its coordinates at once, and these shifts must be equal to each other by their absolute values. A queen in N-dimensional chess can make its move both as a bishop and as a rook.
A queen is situated on empty chess-board in a cell with coordinates (C[1], C[2], ..., C[N]). You should calculate a number of different cells the queen can make its move to.


The first line contains the integer numbers N (1 ≤ N ≤ 10000) and S (2 ≤ S ≤ 100000). The second line contains N integer numbers C[i] (1 ≤ C[i] ≤ S).


You should output the solution of "Queen I" problem.


3 3
1 2 3


Let us consider three-dimensional chess-board 3*3*3 cells in size. If a queen is initially located in the cell with coordinates (1, 2, 3) it can make its move to the cells with coordinates (2, 2, 3), (3, 2, 3), (1, 1, 3), (1, 3, 3), (1, 2, 1) and (1, 2, 2) moving as a rook, and to the cells with coordinates (2, 3, 2) and (2, 1, 2) moving as a bishop.
Problem Author: Dmitry Kovalioff, Ilya Grebnov, Nikita Rybak
Problem Source: Timus Top Coders: Second Challenge
To submit the solution for this problem go to the Problem set: 1453. Queen