UTPC is making friendship bracelets for an upcoming fair.
There are $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) beads arranged in a row. The $$$i$$$-th bead has color $$$a_i$$$ ($$$1 \le a_i \le n$$$). A bracelet consists of a contiguous group of at least two beads, and the first and last beads in the bracelet must have the same color.
A bracelet containing $$$k$$$ beads earns $$$k$$$ dollars, but making a bracelet costs $$$c$$$ ($$$0 \le c \le 10^9$$$) dollars. You may make any number of bracelets, as long as no bead belongs to more than one bracelet. Beads not included in a bracelet earn nothing.
What is the maximum total profit you can earn? You may also choose to make no bracelets.
The first line contains two integers $$$n$$$ and $$$c$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le c \le 10^9$$$), the number of beads and the cost of assembling one bracelet.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$), where $$$a_i$$$ is the color of the $$$i$$$-th bead.
Print one integer: the maximum possible total profit from making non-overlapping valid bracelets.
9 21 2 1 3 3 4 4 3 9
4
One optimal choice is to make a bracelet using beads at positions $$$1$$$ through $$$3$$$, and another using beads at positions $$$4$$$ through $$$8$$$. Their profits are $$$3-2=1$$$ and $$$5-2=3$$$, for a total of $$$4$$$. The last bead is unused.
| Name |
|---|


