Война
시간 제한2초메모리 제한256 MB
솔더들의 키 수열을 연속한 여러 구간으로 나누되, 각 구간은 키가 단조이면 길이만큼, 아니면 0의 점수를 얻는다. 구간 점수의 곱이 최대가 되는 분할 하나를 출력한다.
문제
На одну маленькую нефтеносную страну было совершено нападение высокотехнологичной армии другой враждебной страны. Для защиты была мобилизована армия, состоящая из n солдат. Перед началом решающего боя все n солдат выстроились в шеренгу перед генералом. Он всегда считал, что все солдаты в его войске одинакового роста, однако это оказалось не так. Генерал понял, что такая армия малоэффективна, и решил разбить ее на подразделения. Под подразделениями генерал подразумевал непустые группы солдат, стоящих друг за другом в шеренге. Также генерал решил ввести понятие "мощность подразделения", которое определялось как:
- количество солдат в подразделении, если в шеренге они стоят в порядке невозрастания или неубывания их роста;
- 0 в противном случае.
Также генерал решил, что мощность армии равна произведению мощностей всех подразделений.
Генерал хочет найти такое разбиение армии на подразделения, чтобы мощность всей армии была максимальна. Помогите ему решить эту задачу.
입력
Первая строка содержит целое число n (1 ≤ n ≤ 50000)— количество солдат. В следующей строке содержится n целых чисел ai (0 ≤ ai ≤ 109) — рост i-го солдата.
출력
В первой строке выведете число k — количество подразделений, на которое генералу следует раздить шеренгу. Во второй строке следует вывести k чисел bi — номер в шеренге самого правого солдата в i-м подразделении. Числа надо вывести в порядке возрастания. Если существует несколько разбиений, то можно вывести любое разбиение.