Bombone - Državno

Little Djole saw n sweets in a candy shop's window. The sweets are lined up and each one of them is represented with a single natural number - different numbers indicate different types of sweets, and same numbers indicate the same kind of sweets. He plans to grab some of them, eventually pay for them and later sweeten himself up.

In order to do it faster, he wants to grab only a sequence of successive sweets, i.e. he wants to select two integers i and j (1 ≤ i ≤ j ≤ n) and grab all the sweets on the positions i, i + 1, ..., j - 1, j. Also, since he doesn't like diversity, there may not be more than three different kinds of sweets in that subsequence. For example, the subsequence 12434 is not a good one because it contains 4 different kinds of candy.

Determine the amount of ways Djole can grab the sweets.