Задача №3, тоже посложнее, «Война». Решена правильно Капуном Евгением на 16-й минуте.
«На одну маленькую нефтеносную страну было совершено нападение высокотехнологичной армии другой враждебной страны. Для защиты была мобилизована армия, состоящая из n солдат. Перед началом решающего боя все n солдат выстроились в шеренгу перед генералом. Он всегда считал, что все солдаты в его войске одинакового роста, однако это оказалось не так. Генерал понял, что такая армия малоэффективна, и решил разбить ее на подразделения. Под подразделениями генерал подразумевал непустые группы солдат, стоящих друг за другом в шеренге. Также генерал решил ввести понятие “мощность подразделения”, которое определялось как:
* количество солдат в подразделении, если в шеренге они стоят в порядке невозрастания или неубывания их роста;
* 0 в противном случае.
Также генерал решил, что мощность армии равна произведению мощностей всех подразделений.
Генерал хочет найти такое разбиение армии на подразделения, чтобы мощность всей армии была максимальна. Помогите ему решить эту задачу.
Первая строка содержит целое число n (1 ≤ n ≤ 50000)— количество солдат. В следующей строке содержится n целых чисел ai (0 ≤ ai ≤ 109) — рост i-го солдата.
В первой строке выведете число k — количество подразделений, на которое генералу следует раздить шеренгу. Во второй строке следует вывести k чисел bi — номер в шеренге самого правого солдата в i-м подразделении. Числа надо вывести в порядке возрастания. Если существует несколько разбиений, то можно вывести любое разбиение.
Например, при следующих входных данных
5
1 2 3 5 4
нужно выводить
2
3 5
»
Being in America 