Алиса и Боб играют в игру на прямой с \(n\) ячейками. Есть \(n\) ячеек, пронумерованных от \(1\) до \(n\). Для каждого \(i\) от \(1\) до \(n-1\) ячейки \(i\) и \(i+1\) являются смежными.
У Алисы изначально есть фишка в какой-то ячейке на прямой, а Боб пытается угадать, где она находится.
Боб спрашивает последовательность номеров ячеек в таком порядке: \(x_1, x_2, \ldots, x_k\). В \(i\)-м вопросе Боб спрашивает Алису, находится ли ее фишка в ячейке \(x_i\). То есть, Алиса ответит либо «нет», либо «да» на каждый вопрос Боба.
Не более одного раза в этом процессе, до или после ответа на вопрос, Алиса может переместить свою фишку из своей текущей ячейки в некоторую смежную ячейку. Алиса действует так, чтобы она могла ответить «нет» на все вопросы Боба.
Обратите внимание, что Алиса даже может переместить свою фигурку, прежде чем ответить на первый вопрос или после того, как ответит на последний вопрос. Алиса также может вообще не передвигать ее.
Вам дано число \(n\) и вопросы Боба \(x_1, \ldots, x_k\). Вы хотели бы посчитать количество сценариев, которые позволяют Алисе ответить «нет» на все вопросы Боба.
Пусть \((a,b)\) обозначает сценарий, в котором Алиса начинает в ячейке \(a\) и заканчивает в ячейке \(b\). Два сценария \((a_i, b_i)\) и \((a_j, b_j)\) различны, если \(a_i \neq a_j\) или \(b_i \neq b_j\).
Выходные данные
Выведите единственное целое число — количество сценариев, которые позволяют Алисе ответить «нет» на все вопросы Боба.
Примечание
Пусть \((i,j)\) обозначает сценарий, в котором Алиса начинает в ячейке \(i\) и заканчивает в ячейке \(j\).
В первом примере нам подходят сценарии: \((1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3), (3, 4), (4, 3), (4, 5)\). Например, \((3,4)\) нам подходит, поскольку Алиса может начать в ячейки \(3\), остаться там в течение первых трех вопросов, а затем перейти в ячейку \(4\) после последнего вопроса.
\((4,5)\) нам подходит, поскольку Алиса может начать в ячейки \(4\), остаться там до первого вопроса, после которого перейти в ячейку \(5\) и остаться там, когда Боб спрашивает следующие два вопроса. Обратите внимание, что \((4,5)\) учитывается только один раз, хотя есть и другие вопросы, после которых Алиса может переместить фишку, но помните, что каждая пара начальных и конечных позиций учитывается только один раз.
Во втором примере ни один сценарий нам не подходит.
В последнем примере все \((i,j)\), где \(|i-j| \leq 1\), за исключением \((42, 42)\), нам подходят.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
5 1 4
|
9
|
|
2
|
4 8
1 2 3 4 4 3 2 1
|
0
|
|
3
|
100000 1
42
|
299997
|