Изменения

# <tex>count > 0</tex> и <tex>a[k+1] = candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу равенства <tex>a[k+1]</tex> и <tex>candidate</tex>, если на подмассиве <tex>a[0..(k+1)]</tex> существует мажорирующий элемент, то он тоже будет равен <tex>candidate</tex>.</p>

# <tex>count > 0</tex> и <tex>a[k+1] != candidate</tex><p>Если на подмассиве <tex>a[0..k]</tex> существует мажорирующий элемент, то он находится в <tex>candidate</tex>. Тогда, в силу неравенства <tex>a[k+1]</tex> и <tex>candidate</tex>, образовалась новая пара. Если <tex>count</tex> не станет равным нулю, то опять же мажорирующим элементом может быть только candidate, так как для всех остальных мы нашли пару, а значит встречаются они не более <tex>N/2</tex> раз.</p>

== Обобщение на случай поиска элемента, встречающегося N/K раз ==