Statement

Giorgio enjoys doing endless statistical calculations in his spare time. Today, he collected the history of songs he ever played on his laptop, and started wondering about the many different music genres he followed during these last years. In particular, the list comprises N songs ordered chronologically, each of them tagged with a music genre G_i. Giorgio define as a trend at time i = 1 … N any music genre which was a mode among the genres G_0, …, G_i-1 (that is, among the songs played before time i). How many different music genres were a trend at any past point in time?