Разбиения числа \(n\) на слагаемые — это набор целых положительных чисел, сумма которых равна \(n\). При этом разбиения, отличающиеся лишь порядком слагаемых, считаются одинаковыми, поэтому можно считать, что слагаемые в разбиении упорядочены по неубыванию.

Например, существует 7 разбиений числа 5 на слагаемые:

В приведенном примере разбиения упорядочены лексикографически — сначала по первому слагаемому в разбиении, затем по второму, и так далее. В этой задаче вам потребуется по заданному разбиению на слагаемые найти следующее в лексикографическом порядке разбиение.

Недавно разведка Флатландии перехватила секретный документ. Сотрудники первого отдела разведки подозревают, что это список пар городов, между которыми в соседней Берляндии проложены автомагистрали. Попытавшись сопоставить номера городов с городами Берляндии, сотрудники убедились что это можно сделать.

Однако сотрудники второго отдела высказали другое предположение. Они предположили, что этот список — это в точности список пар городов, между которыми в Берляндии нет автомагистрали. Попытавшись сопоставить номера городов с городами в Берляндии, они также убедились, что это можно сделать.

Директор разведки в затруднении. Решив проверить, возможно ли такое, он дал задание сотрудникам третьего отдела. Директор попросил их выяснить, может ли так быть, что между некоторыми городами в Берляндии проложены автомагистрали, а между некоторыми — нет, и существует самодвойственный список пар. Список пар целых чисел от 1 до \(n\) называется самодвойственным, если можно занумеровать города так, чтобы он задавал все пары городов, между которыми есть автомагистраль, а можно перенумеровать города таким образом, чтобы тот же самый список задавал все пары городов, между которыми автомагистрали нет.

Помогите сотрудникам третьего отдела решить поставленную задачу.

В цирке планируется грандиозное театрализованное шоу с участием львов и тигров. Чтобы уменьшить агрессию хищников, дрессировщики хотят составить программу таким образом, чтобы львы и тигры никогда не встречались на сцене.

Шоу состоит из \(n\) небольших представлений, в каждом из которых могут участвовать или львы, или тигры (также может случиться, что в представлении не участвуют ни те, ни другие). Представление \(i\) начинается через \(s_i\) минут от начала шоу и продолжается \(t_i\) минут. При этом в некоторые моменты времени на сцене могут идти одновременно несколько представлений (в этом случае в них не могут участвовать разные виды хищников).

Публика любит и представления со львами, и представления с тиграми. Дрессировщики просят вас помочь им распределить представления между львами и тиграми так, чтобы минимум из числа представлений с львами и числа представлений с тиграми был как можно больше.

Олег — известный поклонник соревнований по программированию. Он знает всех участников всех соревнований за последние десять лет и может про любого участника сказать, сколько задач решила команда с его участием на любом соревновании. И еще Олег очень любит теорию чисел.

В таблице результатов соревнования по программированию команды упорядочены по убыванию количества решенных задач. Олег называет таблицу результатов красивой, если для всех команд количество решенных ими задач равно нулю или является делителем количества задач на соревновании. Когда какая-нибудь команда сдает задачу, количество сданных задач у нее увеличивается на один. Никакая команда не может сдать две или более задач одновременно, также две команды не могут одновременно сдать задачу.

Глядя на красивую таблицу результатов, Олег заинтересовался: а сколько еще задач смогут суммарно сдать команды так, чтобы после каждой сданной задачи таблица результатов оставалась красивой? Помогите ему выяснить это.