Запасы на зиму

시간 제한2초메모리 제한1024 MB

요약

n개의 구간 [l_i, r_i]이 주어질 때, 서로 겹치지 않게 (끝점이 닿는 것은 허용) 순서대로 방문할 수 있는 최대 구간 집합과 그 방문 순서를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

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

Эдвард знает $n$ пунктов, в которых он сможет достать кровь. Одна проблема --- пункты работают только в определeнные моменты времени. Пункт номер $i$ работает только с $l\_i$ минуты по $r\_i$ . Эдвард получит кровь в этом пункте только в том случае, если пробудет в нeм всe время работы, то есть в минуты с номерами с $l\_i$ по $r\_i$ .

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

Во всех пунктах Эдвард получает одинаковое количество крови.

입력

В первой строке входного файла дано число $n$ ( $1 \le n \le 10^5$ ) --- количество пунктов сдачи крови. В каждой из следующих $n$ строк записано два числа $l\_i$ и $r\_i$ ( $1 \le l\_i < r\_i \le 10^9$ ) --- моменты времени, в которые работает пункт сдачи крови номер $i$ .

출력

В первой строке выходного файла выведите максимальное количество пунктов сдачи крови, которые сможет посетить Эдвард. Во второй строке выведите номера этих пунктов. Номера выводите в том порядке, в котором Эдвард будет их посещать. Пункты нумеруются с 1 в порядке, в котором они заданы во входном файле.

Если ответов несколько, разрешается вывести любой.

힌트

В первом тестовом примере Эдварду ничего не мешает сначала посетить первый пункт сдачи крови, а затем второй.

Во втором примере он может сначала побывать в первом пункте в моменты времени с 1 до 4 и сразу же, в момент времени 4, оказаться в четвертом пункте.

예제2

예제 1
입력
```
2
1 2
3 4
```
예상 출력
```
2
1 2
```
예제 2
입력
```
4
1 4
2 5
3 6
4 7
```
예상 출력
```
2
1 4
```