Определим \(\operatorname{MAD}\) (Максимальное Повторяющееся Значение) в массиве как наибольшее число, которое присутствует в массиве хотя бы дважды. Если нет такого числа, которое присутствует в массиве хотя бы дважды, значение \(\operatorname{MAD}\) равно \(0\).
Например, \(\operatorname{MAD}([1, 2, 1]) = 1\), \(\operatorname{MAD}([2, 2, 3, 3]) = 3\), \(\operatorname{MAD}([1, 2, 3, 4]) = 0\).
Вам дан массив \(a\) размера \(n\). Изначально переменная \(sum\) равна \(0\).
Следующий процесс будет выполняться, пока все числа в массиве \(a\) не станут равными \(0\):
- Присвоить \(sum := sum + \sum_{i=1}^{n} a_i\);
- Пусть \(b\) — массив размера \(n\). Присвоим \(b_i :=\ \operatorname{MAD}([a_1, a_2, \ldots, a_i])\) для всех \(1 \le i \le n\), затем присвоим \(a_i := b_i\) для всех \(1 \le i \le n\).
Найдите значение \(sum\) после выполнения процесса.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите финальное значение \(sum\).
Примечание
В первом наборе входных данных, изначально \(a=[1]\).
В первом цикле:
- Присвоим \(sum := sum + a_1 = 0+1=1\);
- Присвоим \(b_1 :=\ \operatorname{MAD}([a_1])=\ \operatorname{MAD}([1])=0\), затем присвоим \(a_1 := b_1\).
После первого цикла, \(a=[0]\) и процесс завершается. Значение \(sum\) после процесса равно \(1\).
Во втором наборе входных данных, изначально \(a=[2,2,3]\).
После первого цикла, \(a=[0,2,2]\) и \(sum=7\).
После второго цикла, \(a=[0,0,2]\) и \(sum=11\).
После третьего цикла, \(a=[0,0,0]\) и \(sum=13\). После этого процесс завершается.
Финальное значение \(sum\) равно \(13\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1
3
2 2 3
4
2 1 1 2
4
4 4 4 4
|
1
13
9
40
|