교장선생님은 중요한 작업을 수행해야 합니다 - 몇 번 학생을 학생회장으로 뽑아야 하는지 결정하는 것입니다.

학교의 N명의 학생들 (2 \le N \le 10^5)은 1부터 N까지 번호가 매겨져 있으며, 각 학생는 정확히 한 명의 학생회장 후보 h_i (1 \le h_i \le N)를 지지합니다. 그는 모든 학생들이 같은 후보를 지지하도록 하고 싶어합니다.

이를 위해 교장선생님은 의견 교환을 개최할 수 있습니다. 의견 교환은 번호가 i부터 j까지인 연속된 범위의 모든 학생들을 모아 회의를 하는 것입니다. 만약 그룹 내에서 과반수 이상의 학생들이 지지하는 후보가 있다면, 회의가 끝난 후 모든 학생들은 그 후보를 지지하게 됩니다. 그런 후보가 없다면, 학생들은 지지하는 후보를 바꾸지 않습니다. 예를 들어, 16명의 학생으로 구성된 의견 교환에서는 9명 이상이 같은 후보를 지지해야 나머지 학생들이 그에 맞춰 지지하는 학생을 바꿉니다.

교장선생님은 모든 학생들이 동시에 좋아할 수 있는 후보가 누구인지 알고 싶어합니다. 그는 한 번에 하나의 의견 교환만 개최할 수 있지만, 필요한 만큼 의견 교환을 운영할 수 있습니다.

#6213 upload 8 done 4 how_to_reg 4 call_split Subtask

학생회장 후보선출 timer 2s memory 1024MB

#6213
Subtask

학생회장 후보선출 2s 1024MB