Fermer Conun Birləşmiş İnekleri (Qızıl)
n inək nümayəndə heyətinin seçilməsində iştirak edir. Onlar bir sırada dayanır və i inəyin cinsi b[i] ilə təmsil olunur.
Nümayəndə heyəti ən azı iki inəkdən ibarət olan ardıcıl bir intervaldan ibarətdir - yəni tam l və r üçün l..r inəklərindən, burada 1 ≤ l < r ≤ n. Seçilmiş intervalın iki xarici inəyi "liderlər" adlanır. İnek cinsləri arasında münaqişədən qaçmaq üçün hər bir lider nümayəndə heyətinin (liderlər və qeyri-liderlər) qalan inəklərindən fərqli bir cinsə sahib olmalıdır.
Nümayəndə heyətini seçməyin neçə yolu olduğunu müəyyən edin.
Giriş məlumatları
Birinci sətir n (1 ≤ n ≤ 2 * 10^5) ehtiva edir.
İkinci sətir n tam ədədləri b[1], b[2], .., b[n] ehtiva edir, hər biri [1, n] intervalında.
Çıxış məlumatları
Mümkün nümayəndə heyətlərinin sayını çıxarın.
Nümunə
Hər bir nümayəndə heyəti aşağıdakı lider cütlərindən birinə uyğundur:
(1, 2), (1, 3), (1, 4), (1, 7), (2, 3), (2, 4), (3, 4), (4, 5), (4, 6), (4, 7), (5, 6), (5, 7), (6, 7).