Иахуб саяхан $n$ ширхэг $a_{1}$, $a_{2}$, ..., $a_{n}$ элементтэй сэлгэмэлийг өсөх дарааллаар эрэмбэлэдэг алгоритм болох бөмбөлгөн эрэмбэлэлтийг сурсан. Тэр энэ алгоритм маш хялбар учраас уйдсан ба тэр өөрийн гэсэн граф зохиосон. Граф анх (графыг $G$ гэе) $n$ оройтой 0 ирмэгтэй байсан. Бөмбөлгөн эрэмбэлэлтийн үеэр ирмэгүүд дараах алгоритмд тодорхойлогдсоноор гарч ирнэ (псеудокод).

procedure bubbleSortGraph()  
    build a graph G with n vertices and 0 edges  
    repeat  
        swapped = false  
        for i = 1 to n - 1 inclusive do:  
            if a[i] > a[i + 1] then  
                add an undirected edge in G between a[i] and a[i + 1]  
                swap( a[i], a[i + 1] )  
                swapped = true  
            end if  
        end for  
    until not swapped   
    /* repeat the algorithm as long as swapped value is true. */   
end procedure

Графын хувьд бие даасан бүрдэл гэдэг нь ямар ч хоёр нь хөрш биш графын оройнуудын бүрдэл байна (мөн бие даасан бүрдлийн оройнуудын хооронд ямар ч ирмэг байхгүй). Хамгийн их бие даасан бүрдэл нь хамгийн олон элементтэй бүрдэл байна. Өгөгдсөн сэлгэмэлийн хувьд хэрвээ бид энэ сэлгэмэлийг bubbleSortGraph процедурын $a$ сэлгэмэлээр ашигласан бол $G$ графын хамгийн их бие даасан бүрдлийн хэмжээг ол.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($2 ≤ n ≤ 10^{5}$) байна. Дараагийн мөрөнд $n$ ширхэг ялгаатай бүхэл тоон утга $a_{1}$, $a_{2}$, ..., $a_{n}$ $(1 ≤ a_{i} ≤ n)$ байна.

Гаралт

Бодлогын хариу болох нэг ширхэг бүхэл тоон утгыг хэвлэ.

Эхний жишээг авч үзье. Бөмбөлгөн эрэмбэлэлт 3 ба 1 элементүүдийг солино. Бид (1, 3) ирмэгийг нэмнэ. Сэлгэмэл одоо [1, 3, 2] байна. Тэгээд бөмбөлгөн эрэмбэлэлт 3 ба 2 элементүүдийг солино. Сэлгэмэл одоо [1, 3, 2] байна. Бид (2, 3) ирмэгийг нэмнэ. Сэлгэмэл одоо эрэмбэлэгдсэн байна. Бидэнд 3 орой болон (1, 3) ба (2, 3) гэсэн 2 ирмэгтэй граф байна. Үүний хамгийн их бие даасан бүрдэл нь [1, 2] байна.