A radio station tags each song of its playlist with a genre number, in order, in genres. The
variety of a stretch of consecutive songs is the number of different genres in it. Return
the total variety over every non-empty stretch of consecutive songs (a playlist of n songs
has n * (n + 1) // 2 stretches). An empty playlist gives 0.
Examples
Input: genres = [1, 2, 1]
Output: 9
Explanation: [1], [2] and [1] have variety 1 each; [1, 2], [2, 1] and [1, 2, 1] have variety
2 each. Total 3 + 6 = 9.
Input: genres = [4, 4, 4]
Output: 6
Explanation: all six stretches hold a single genre.
Input: genres = []
Output: 0
Constraints
0 <= len(genres) <= 10**5-10**9 <= genres[i] <= 10**9- Target: O(n) time. Building a set for every stretch is far too slow for the largest tests.
Goals
- Count how many stretches each element is responsible for
- Credit a value only at its first appearance inside a stretch
- Use a last-seen dict to avoid a quadratic scan