У Tokitsukaze есть последовательность \(a\) длины \(n\). Для каждой операции она выбирает два числа \(a_i\) и \(a_j\) (\(i \ne j\); \(1 \leq i,j \leq n\)).
- Если \(a_i = a_j\), измените одно из них на \(0\).
- В противном случае измените их оба на \(\min(a_i, a_j)\).
Tokitsukaze хочет узнать, за какое минимальное количество операций можно изменить все числа в последовательности на \(0\). Можно доказать, что ответ всегда существует.
Примечание
В первом наборе входных данных один из возможных способов изменить все числа в последовательности на \(0\):
В \(1\)-й операции \(a_1 < a_2\), после операции \(a_2 = a_1 = 1\). Теперь последовательность \(a\) равна \([1,1,3]\).
В \(2\)-й операции \(a_1 = a_2 = 1\), после операции \(a_1 = 0\). Теперь последовательность \(a\) равна \([0,1,3]\).
В \(3\)-й операции \(a_1 < a_2\), после операции \(a_2 = 0\). Теперь последовательность \(a\) равна \([0,0,3]\).
В \(4\)-й операции \(a_2 < a_3\), после операции \(a_3 = 0\). Теперь последовательность \(a\) равна \([0,0,0]\).
Таким образом, минимальное количество операций составляет \(4\).