Stack

Se dă un șir, $s$, de mărime $N$ cu elemente din mulțimea $\{0, 1, 2, \ldots, M - 1\}$. Definim funcția de compresie a unul șir astfel:

function compress(s)
	stk ← []
	for i ← 0 ... len(s) − 1 do
		if s[i] = ultimul element din stk then
			șterge ultimul element din stk
		else
			stk ← stk + s[i]
		end if
	end for
	return len(stk)
end function

Cerință

Vom nota cu $s[i\dots j]$ secvența contiguă a lui $s$ obținută prin eliminarea prefixului $s_0, s_1, \dots s_{i-1}$ și a sufixului $s_{j+1}, s_{j+2}, \dots s_{N-1}$.

Să se calculeze

De vreme ce acest număr poate deveni foarte mare, se cere restul împărțirii sale la $2^{64}$.

Detalii de implementare

Va trebui să implementezi funcția

std::uint64_t sum_compressed_lengths(std::vector<int> s, int M);

care:

• primește ca parametri șirul $s$ și $M$, cu semnificația din enunț;
• returnează suma cerută modulo $2^{64}$.

Comisia va apela funcția o singură dată per test.

Restricții și precizări

• $1 \leq M \leq N \leq 5 \ 000 \ 000$
• $0 \leq s_i < M$

Exemplu

input

10 5
2 2 3 3 4 4 1 1 4 3

output

64