30. Индекс септаккорда (2.0)

Музыкант и композитор Ледоне уже не первый год поражает мировое музыкальное сообщество своими творческими находками. Искусствоведы бьются над разгадкой секрета гениальности Ледоне и пригласили вас помочь в поиске ответа. Ледоне создаёт музыкальные композиции, используя разные сочетания аккордов. Искусствоведы считают, что септаккорды создают особое звучание произведений Ледоне. Вам нужно определить при помощи индекса септаккорда, насколько часто такие сочетания звуков встречаются в произведениях композитора. У вас есть набор $n$ произведений с числами септаккордов $a_1, a_2, ..., a_n$. Обозначим за $I({\ell}, r)$ $-$ индекс септаккорда последовательности $a_{\ell}, a_{{\ell} + 1}, ..., a_r$ $-$ такое максимальное число произведений $k$ среди произведений с последовательными номерами от $\ell$ до $r$, что в каждом из них содержится хотя бы $k^2$ септаккордов. Теперь ваша задача $-$ посчитать сумму индексов септаккорда по всем непрерывным подпоследовательностям исходной последовательности. То есть найдите $\sum\limits_{\ell = 1}^n \sum\limits_{r = \ell}^n I(\ell, r)$

В первой строке вводится число $1 \le n \le 10^5$. Во второй строке вводится набор целых чисел $a_i$ ($0 \le a_i \le 10^5$) через пробел.

Необходимо вывести сумму индексов септаккорда по всем подотрезкам исходной последовательности произведений.

Рассмотрим первый пример.

, так как в этих подотрезках по одному произведению, каждое из которых имеет индекс септаккорда, больше либо равный $1$.

, так как в этих подотрезках по два произведения, каждое из которых имеет индекс септаккорда, больше либо равный $4$.

, так как в этих подотрезках по три произведения, каждое из которых имеет индекс, больше либо равный $9$.

, так как есть хотя бы три произведения(например, с индексами септаккордов $9, 10, 9$), каждое из которых больше либо равно $9$. Заметим, что индекс септаккорда этого подотрезка не может быть равен $4$, так как тогда у нас должно было бы быть на подотрезке $4$ произведения, индексы септаккорда которых больше либо равны $16$, что не выполняется.