Арсенал

면접 대비

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

요약

일렬로 놓인 화살을 모두 뽑되, 양옆에 더 짧은 화살이 없는 불편한 뽑기 횟수가 최소가 되도록 뽑는 순서를 정한다.

난이도: 보통10점 중 5점
유형: 배열, 그리디, 재귀, 스택
정답자: 아직 제출이 없습니다

문제

Во время очередной тренировки к играм Китнисс решила потренироваться в стрельбе из лука.

В тренировочном зале есть $n$ стрел разной длины, которые находятся в стойках рядом друг с другом вдоль стены. Китнисс хочет выстрелить все стрелы, при этом после каждого выстрела ей придется брать новую стрелу из стойки, а взятые стрелы никогда не возвращаются обратно. Китнисс считает, что стрелу удобно взять, если рядом с ней с обеих сторон стоят стрелы, размеры которых меньше. Отсутствие стрелы с одной из сторон равносильно присутствию стрелы с длиной ноль.

Чтобы процесс тренировки прошел наиболее эффективно, Китнисс хочет взять как можно меньше неудобных стрел. Но так как, ей нужно тренироваться, она просит вас ей помочь подобрать порядок выбора стрел из стоек, чтобы количество неудобно взятых стрел было наименьшим возможным.

입력

В первой строке входного файла дано одно натуральное число $n$ ( $1 \le n \le 10^5$ ) --- количество стоек со стрелами.

Во второй строке дано $n$ чисел $a\_i$ ( $1 \le a\_i \le 1000$ ) --- высота стрел.

출력

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

Во второй строке через пробел выведите $n$ чисел --- номера стрел в порядке, в котором Китнисс будет их брать. Если способов взять стрелы несколько, выведите любой.

예제3

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