Изменения

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