Liderzy
면접 대비시간 제한3초메모리 제한1024 MB
주어진 수열을 여러 부분수열로 나눌 때, 각 부분수열이 과반수 원소를 가지도록 하는 최소 부분수열 개수를 구한다.
문제
Według słownika PWN „lider” to między innymi „przywódca partii politycznej, związku zawodowego lub innych organizacji społecznych”. Natomiast w algorytmice liderem ciągu elementów nazywamy element, którego liczba wystąpień jest ściśle większa od połowy długości ciągu. Dla przykładu, liderem ciągu [7, 2, 5, 7, 7] jest liczba 7, zaś ciąg [2, 3, 2, 3] nie posiada lidera w ogóle.
W tym zadaniu skupimy się na tym drugim znaczeniu słowa „lider”. Mając dany ciąg liczb, Twoim zadaniem jest podzielić go na minimalną liczbę ciągów (niekoniecznie spójnych), z których każdy posiada lidera, i wypisać tę minimalną liczbę. Można wykazać, że taki podział jest zawsze możliwy.
입력
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 500 000), oznaczająca długość ciągu.
W drugim wierszu wejścia znajduje się ciąg n liczb całkowitych a1, a2, . . . , an (1 ≤ ai ≤ n).
출력
W jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita, oznaczająca minimalną możliwą liczbę ciągów, na które można podzielić wejściowy ciąg tak, aby każdy wynikowy ciąg posiadał lidera.
힌트
Wyjaśnienie przykładu: Wejściowy ciąg można podzielić na przykład na ciągi [1, 3, 1] i [2, 2]. W ten sposób oba wynikowe ciągi będą posiadały lidera (odpowiednio liczby 1 i 2).