ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1453. Ферзь

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ

Вступление

Годы и годы минули с тех пор, как известный гроссмейстер Павел Васильевич Пешкин создал N-мерные шахматы и сформулировал для них классическую задачу "Ферзь II". С тех пор сотни исследователей пытались познать её непостижимую суть и докопаться до решения, но лишь немногие в итоге достигли цели. Остальные, как водится, начали ныть, жаловаться на непомерную сложность задачи - и вообще вели себя очень некрасиво. "Дайте что-нибудь попроще! Ну пусть хотя бы будет не два хода, а один, а?", - требовали эти несознательные товарищи.
Но гроссмейстер предвидел и это. Он знал, что масштабируемость ограничений - великая вещь. И словно желая поиздеваться над любителями халявы, г-н Пешкин предложил международной общественности задачу, известную под названием "Ферзь I".

Задача

Доска в N-мерных шахматах представляет собой N-мерный куб размером S*S*...*S ячеек. Ячейка в одном - выбираемом произвольно - из углов этого куба имеет координаты (1, 1, ..., 1), а ячейка в противоположном углу - координаты (S, S, ..., S).
Ладья в N-мерных шахматах ходит, смещаясь на произвольное ненулевое количество ячеек по одной из своих координат. Слон в N-мерных шахматах ходит, смещаясь на произвольное ненулевое количество ячеек по всем N координатам одновременно, причём смещения по всем координатам должны быть равны по модулю. Ферзь в N-мерных шахматах может ходить и как ладья, и как слон.
Ферзь находится на пустой шахматной доске в ячейке с координатами (C[1], C[2], ..., C[N]). Необходимо определить количество различных ячеек, в которые он может сделать свой ход.

Исходные данные

Первая строка содержит целые числа N (1 ≤ N ≤ 10000) и S (2 ≤ S ≤ 100000). Вторая строка содержит N целых чисел C[i] (1 ≤ C[i] ≤ S).

Результат

Вывести решение задачи "Ферзь I".

Пример

исходные данныерезультат
3 3
1 2 3
8

Замечания

Рассмотрим трёхмерную шахматную доску размером 3*3*3 ячейки. Если изначально ферзь находится в ячейке с координатами (1, 2, 3), то свой ход он может сделать в ячейки с координатами (2, 2, 3), (3, 2, 3), (1, 1, 3), (1, 3, 3), (1, 2, 1) и (1, 2, 2), двигаясь, как ладья, и в ячейки с координатами (2, 3, 2) и (2, 1, 2), двигаясь, как слон.
Автор задачи: Дмитрий Ковалёв, Илья Гребнов, Никита Рыбак
Источник задачи: Timus Top Coders: Second Challenge