Niyə inək yolu keçdi (Platin)
Fermer Con n fərqli cins inək yetişdirir və hər bir tarla müəyyən bir inək cinsi üçün otlaq kimi nəzərdə tutulub. Məsələn, 12 cinsli inəklər üçün nəzərdə tutulmuş tarla yalnız 12 cinsli inəklər üçün istifadə edilə bilər. Uzun bir yol fermadan keçir və yolun hər iki tərəfində n tarladan ibarət ardıcıllıq var, hər biri fərqli bir cins üçün nəzərdə tutulub. İnəklər yolu keçərkən, bir tarladan həmin cins üçün nəzərdə tutulmuş digər tarlaya keçirlər.
Əgər Con əvvəlcədən planlaşdırmış olsaydı, tarlaları elə düzəldə bilərdi ki, yolun hər iki tərəfində eyni cins üçün nəzərdə tutulmuş tarlalar bir-birinin qarşısında yerləşərdi və inəklər yolu keçərkən toqquşmazdılar. Lakin, tarlaların düzülüşü fərqli ola bilər və bu zaman yolun keçidində yolları kəsişən cinslər cütləri ola bilər. Fərqli cinslərdən olan bir cüt (a, b) "kəsişən" adlanır, əgər a cinsli inəyin yolun qarşısına keçməsi üçün hər hansı bir yolu, b cinsli inəyin yolun qarşısına keçməsi üçün hər hansı bir yolu ilə kəsişirsə.
Con kəsişən cinslər cütlərinin sayını minimuma endirmək istəyir. Logistik səbəblərə görə, Con yolun bir tərəfindəki tarlaları "dairəvi şəkildə" dəyişə bilər, yəni tarlalar "dairəvi sürüşmə" həyata keçirir. Bu, bəzi 0 ≤ k < n üçün hər bir inəyin k tarlaya irəliləməsi və son k tarladakı inəklərin ilk k tarlaya keçməsi deməkdir. Məsələn, yolun bir tərəfindəki tarlalar belə düzülmüşdürsə: 3, 7, 1, 2, 5, 4, 6 və k = 2 sürüşməsi həyata keçirilirsə, yeni düzülüş belə olacaq: 4, 6, 3, 7, 1, 2, 5. Yolun bir tərəfindəki tarlaların uyğun dairəvi sürüşməsindən sonra mövcud ola biləcək minimum kəsişən cinslər cütlərinin sayını müəyyən edin.
Giriş məlumatları
Birinci sətir n ədədini (1 ≤ n ≤ 10^5) ehtiva edir. Növbəti n sətir yolun bir tərəfindəki tarlalarda cinslərin nömrələrinə görə düzülüşünü təsvir edir. Hər bir cins nömrəsi 1 .. n intervalında tam ədəddir. Son n sətir yolun digər tərəfindəki tarlalarda inək cinslərinin nömrələrinə görə düzülüşünü təsvir edir.
Çıxış məlumatları
Yolun bir tərəfindəki tarlaların dairəvi sürüşməsindən sonra mövcud ola biləcək minimum kəsişən cinslər cütlərinin sayını çıxarın (hər hansı bir tərəf sürüşdürülə bilər).