Вам дан массив \(a\) длины \(n\). Цена массива \(a\) — это MEX\(^{\dagger}\) массива \([a_1+a_2,a_2+a_3,\ldots,a_{n-1}+a_n]\). Найдите минимальную цену \(a\), если в нём разрешается переставлять элементы массива \(a\) местами. Обратите внимание, что вам не нужно искать массив \(a\), на котором достигается минимальная цена.
\(^{\dagger}\) MEX (minimum excluded, минимальное отсутствующее) массива — это наименьшее целое неотрицательное целое число, которое не принадлежит массиву. Например:
- MEX массива \([2,2,1]\) равен \(0\), потому что \(0\) не принадлежит массиву.
- MEX массива \([3,1,0,1]\) равен \(2\), потому что \(0\) и \(1\) принадлежат массиву, а \(2\) — нет.
- MEX массива \([0,3,1,2]\) равен \(4\), потому что \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, а \(4\) — нет.
Выходные данные
Для каждого набора входных данных выведите минимальную цену \(a\) после перестановки элементов \(a\) в любом порядке.
Примечание
В первом наборе входных данных оптимальной является перестановка \(a\), равная \([0,0]\), ценой этого массива является MEX массива \([0+0]=[0]\), равный \(1\).
Во втором наборе оптимальной является перестановка \(a\) равная \([0,1,0]\), ценой этого массива является MEX массива \([0+1,1+0]=[1,1]\), равного \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
0 0
3
0 0 1
8
1 0 0 0 2 0 3 0
|
1
0
1
|