Изменения

Пусть данный инвариант выполняется на <tex>k</tex>''-ом'' шаге. Тогда на <tex>(k+1)</tex>''-ом'' шаге возможны 3 варианта:

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

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