После тяжелой работы аналитику Игорю захотелось немного спокойствия.
Он решил завести себе улитку. Для этого он купил аквариум, в середине которого стоял крошечный гладкий ствол дерева и поместил в аквариум улитку, которую он назвал Юля.
Игорь заметил, что иногда Юля пытается подняться по стволу дерева, однако не может этого сделать, так как ствол гладкий. Чтобы помочь улитке, он подвесил на это дерево нитки, прицепив нижний конец i-й нитки на высоте li над землей, а верхний — на высоте ri.
Так получилось, что верхние концы всех ниток располагаются на разной высоте, то есть все ri различны. Теперь Юля может сползать по стволу вниз, а также подниматься вверх от нижнего конца некоторой веревки до верхнего. Игорь остался доволен своей работой, и теперь, когда он хочет отвлечься от работы, он задается вопросами о возможных перемещениях улитки. А именно, его интересуют вопросы следующего вида: «Предположим, сейчас Юля сидит на стволе на высоте x. Как высоко на стволе дерева она сможет оказаться, если никогда не будет опускаться ниже высоты x и никогда не будет подниматься выше высоты y?» Обратите внимание, Юля не может сползать с веревки на ствол до того, как доберется до верха веревки, и Игоря интересует конечное положение Юли на стволе дерева.
Игорь задается различными вопросами, и не всегда может самостоятельно на них ответить. Помогите Игорю, напишите программу, которая отвечает на соответствующие вопросы.