Description

There is a circular necklace with $n$ beads, each bead being one of $k$ colors. Bead $i$ is adjacent to beads $i - 1$ and $i + 1$, and bead $n$ is also adjacent to bead $1$.

Cut the necklace at two positions to split it into two linear segments. For each color, all beads of that color must appear in exactly one of the two segments.

Compute the number of valid ways (it is guaranteed that at least one exists), and the minimum absolute difference between the lengths of the two segments.

Input Format

The first line contains $n, k$ ($2 \leq k \leq n \leq 10^6$). Colors are labeled from $1$ to $k$.

The next $n$ integers, in order, give the color of each bead. (It is guaranteed that each of the $k$ colors appears at least once.)

Output Format

Output one line with two integers: the number of valid ways, and the minimum absolute difference between the lengths of the two segments.

9 5
2 5 3 2 2 4 1 1 3

4 3

Hint

【Sample Explanation】

Among the four ways, the shorter segment is respectively $(5)$, $(4)$, $(1,1)$, $(4,1,1)$. The minimum difference is $6 - 3 = 3$.

Original title: Podział naszyjnika.

Translated by ChatGPT 5