Задача №114747. Лягушка-путешественница
Лягушонок Горф отправился в путешествие по Болотному королевству. К несчастью, он не рассчитал длину своего прыжка и упал в колодец глубиной \(n\) метров. Теперь Горф лежит на самом дне колодца и ему предстоит долгий путь наверх.
Стенки колодца в некоторых местах скользкие, а в некоторых, наоборот, очень удобные. А именно, если Горф сейчас находится на глубине \(x\) метров от уровня земли, то за один прыжок он может подняться на любое расстояние от \(0\) до \(a_x\) метров вверх.
К сожалению, Горф не может прыгать без перерывов. После каждого прыжка ему нужно отдохнуть. Если он отдохнет на глубине \(x\) метров от уровня земли, то за это время проскользит вниз на \(b_x\) метров.
Определите, за какое минимальное число прыжков Горф способен подняться до уровня земли.
В первой строке задано целое положительное число \(n\) (\(1 \le n \le 300\,000\)) — глубина колодца.
Во второй строке задано \(n\) целых чисел \(a_1,\,a_2,\,\ldots,\,a_n\) (\(0 \le a_i \le i\)) — максимальная высота, доступная для прыжка с каждой глубины.
В третьей строке вводится \(n\) целых чисел \(b_1,\,b_2,\,\ldots,\,b_n\) (\(0 \le b_i \le n - i\)) — глубина, на которую лягушонок провалится, взяв перерыв на каждой из глубин.
В первой строке выведите целое число \(k\) — минимально возможное количество прыжков. В случае, если лягушонок не может выбраться из колодца, выведите \(-1\).
Если лягушонок мог выбраться из колодца, то во второй строке выведите последовательность глубин длины \(k\), на которые он будет запрыгивать каждым своим прыжком. Считайте глубину вне колодца в любой точке равной нулю.
Если существует несколько решений, выведите любое из них.
В первом тесте из условия Горф находится на дне колодца, за один прыжок вверх поднимается к отметке в 1 метр глубины. После этого он соскальзывает вниз на метр и оказывается на отметке в 2 метра. С этой отметки он уже сможет выпрыгнуть из колодца за один прыжок.
Во втором тесте из условия Горф может допрыгнуть до отметки в один метр, но сразу после этого соскользнет обратно на дно колодца, поэтому ему не выбраться.
В третьем тесте из условия выбраться из колодца можно только прыгнув с глубины 5. Попасть напрямую туда нельзя, но можно добраться с помощью серии прыжков \(10 \rightarrow 9 \rightarrow 4 \dashrightarrow 5\), где прыжок вверх обозначается простой стрелочкой, а пунктиром обозначен спуск
3 0 2 2 1 1 0
2 1 0
2 1 1 1 0
-1
10 0 1 2 3 5 5 6 7 8 5 9 8 7 1 5 4 3 2 0 0
3 9 4 0