\begin{problem}{Keyins. Вставка ключей}{keyins.in}{keyins.out}{1 секунда}

Дан бесконечный массив, заполненный нулями. В него последовательно
добавляются числа от $1$ до $n$. Для каждого числа задан номер ячейки $a_i$. Если
ячейка номер $a_i$ содержит ноль, то число $i$ записывается в нее. В противном
случае ищется первая ячейка с б\'ольшим номером, содержащая ноль, и число $i$
записывается в нее.

Например, если мы хотим записать число $i$ в третью ячейку, а ячейки со
второй по четвертую заняты, а пятая ячейка свободна, то мы запишем $i$ в пятую
ячейку.

Требуется промоделировать указанный процесс.

\InputFile

Первая строка входного файла содержит натуральное число $n$ --- количество
вставок ($n \leq 500\,000$). Вторая строка содержит $n$ натуральных чисел 
$a_1, \ldots, a_n$ ($a_i\leq 500\,000$).

\OutputFile

Выведите в выходной файл единственное число --- сумму произведений номеров
ячеек на числа в них, взятую по модулю 12345.

\Example

\begin{example}
\exmp{
4
2 4 2 2
}{
39
}%
\end{example}

\end{problem}
