Bombone - Državno

Mali Đole je u izlogu prodavnice slatkiša ugledao n bombona. Bombone su poređane u niz i svaka je predstavljena jednim prirodnim brojem - različiti brojevi označavaju da se radi o različitim vrstama bombona, a isti brojevi označavaju iste vrste bombona. On planira da zgrabi neke od bombona, eventualno plati i kasnije se zasladi.

Radi dobitka na brzini, on želi da zgrabi samo neki uzastopni podniz bombona, tj. da izabere indekse i, j (1 ≤ i ≤ j ≤ n) i da pokupi sve bombone koje se nalaze na pozicijama i, i + 1, ..., j - 1, j. Takođe, pošto ne voli raznolikost, u tom podnizu ne sme biti više od 3 različite vrste bombona. Na primer, podniz 12434 nije dobar jer sadrži 4 vrste bombona.

Odrediti na koliko načina mali Đole može da se zasladi.