Паприка любит перестановки. У неё есть массив \(a_1, a_2, \dots, a_n\). Она хочет сделать массив перестановкой целых чисел от \(1\) до \(n\).
Чтобы достичь этой цели, она может применять к массиву операции. За одну операцию она может выбрать два целых числа \(i\) (\(1 \le i \le n\)) и \(x\) (\(x > 0\)), и затем присвоить \(a_i := a_i \bmod x\) (то есть заменить \(a_i\) на остаток от деления \(a_i\) на \(x\)). В разных операциях выбираемые \(i\) и \(x\) могут быть разными.
Определите минимальное количество операций, необходимое, чтобы сделать массив перестановкой целых чисел от \(1\) до \(n\). Если это невозможно, выведите \(-1\).
Перестановкой называется массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) является перестановкой, но \([1,2,2]\) не является перестановкой (\(2\) встречается дважды в массиве) и \([1,3,4]\) тоже не является перестановкой (\(n=3\), но \(4\) присутствует в массиве).
Выходные данные
Для каждого набора входных данных выведите минимальное количество операций, необходимое, чтобы сделать массив перестановкой целых чисел от \(1\) до \(n\), или \(-1\), если это невозможно.
Примечание
В первом наборе входных данных единственная возможная последовательность операций, минимизирующая количество операций, следующая:
- Выберем \(i=2\), \(x=5\). Заменим \(a_2 := a_2 \bmod 5 = 2\).
Для второго набора входных данных невозможно получить перестановку целых чисел от \(1\) to \(n\).