Necklace Cutting Problem

You are given a circular necklace consisting of n beads. Each bead is colored in one of k colors. The beads are arranged in a circle so that bead 1 is adjacent to bead 2 and bead n, and for any 2 ≤ i ≤ n‐1, bead i is adjacent to beads i-1 and i+1.

You are allowed to make two cuts (i.e. break the necklace at two distinct points between adjacent beads) to split the necklace into two linear chains. The cuts must be chosen such that for every color that appears on the necklace, all beads of that color lie completely in one of the two resulting chains (that is, no color appears partially in both chains).

It is guaranteed that there exists at least one valid way to choose the two cuts satisfying the above condition.

Your task is to compute two numbers:

• The number of valid ways to choose the two cuts.
• Among all valid ways, the minimum possible absolute difference between the lengths of the two resulting chains (where the length is defined as the number of beads in the chain).

Note on the Validity of a cut: In order for the condition to hold (each color confined to a single chain), the cuts must occur only at the boundaries between contiguous segments of beads of the same color. In other words, if the beads of a particular color appear consecutively on the circle (merging the first and last segments if needed), then a valid cut must lie between these segments (and not cutting through the middle of such a contiguous block).

Observation: If you process the necklace by merging all consecutive beads of the same color (remembering to merge the first and last beads if they are the same), then let M be the number of blocks. A valid cut can only be made at the boundaries between these blocks. Hence, the two cuts are chosen from these M boundaries, and the total number of valid ways is simply C(M, 2) = M*(M-1)/2. The second number is the minimum value of |n - 2L| where L is the sum of lengths of one contiguous segment (in terms of blocks) selected by the two cuts (and the other chain automatically has length n - L).

inputFormat

The first line contains two integers n and k — the total number of beads and the number of available colors.

The second line contains n integers. The i-th integer represents the color of the i-th bead in the necklace.

You may assume that the input is such that there exists at least one valid way to break the necklace as described.

outputFormat

Print two space‐separated integers on a single line:

• The total number of valid ways to cut the necklace into two chains.
• The minimum absolute difference in lengths of the two chains among all valid cut schemes.

sample

6 2
1 1 2 2 2 1

1 0