Последовательность

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

요약

주어진 수열에서 순증가하지 않는 가장 긴 부분수열을 찾아 길이와 선택한 인덱스를 출력한다.

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

문제

Задана последовательность из $n$ чисел $a\_1$ , $a\_2$ , $\ldots$ , $a\_n$ . Подпоследовательностью длины $k$ этой последовательности называется набор индексов $i\_1$ , $i\_2$ , $\ldots$ , $i\_k$ , удовлетворяющий неравенствам $1 \le i\_1 < i\_2 < \ldots < i\_k \le n$ . Подпоследовательность называется возрастающей, если выполняются неравенства $a\_{i\_1} < a\_{i\_2} < \ldots < a\_{i\_k}$ .

Широко известна задача поиска максимальной возрастающей подпоследовательности, однако, Вам предлагается решить другую задачу: найти максимальную последовательность данной последовательности, которая не является возрастающей.

입력

В первой строке входного файла находится число $n$ ( $1 \le n \le 100$ ) --- число элементов последовательности. В второй строке находится $n$ чисел $a\_i$ ( $0 \le a\_i \le 1000$ ) --- элементы последовательности.

출력

В первой строке выходного файла выведите $k$ длину максимальной не являющейся возрастающей последовательности или $0$ , если такой не существует. В случае, если искомая подпоследовательность существует, во второй строке выведите $k$ чисел $i\_j$ --- набор индексов подпоследовательности.

예제2

예제 1
입력
```
3
3 2 1
```
예상 출력
```
3
1 2 3
```
예제 2
입력
```
2
1 2
```
예상 출력
```
0
```