28686번 - 감소하는 성장률의 비극 3 스페셜 저지

유림이는 자신의 성장률이 감소한다는 점을 느끼고 매우 슬펐다. 그러던 어느 날, 유림이는 우연히 키를 매우 정밀하게 측정해 주는 비싼 기계에 눈독을 들여 이를 구입하게 되었다. 이 기계는 유림이의 키를 반올림하여 $\mathrm{cm}$ 단위로 소수점 아래 셋째 자리까지 정확하게 표현하였으므로(즉, 오차 범위가 무려 $0.5\times10^{-3}\mathrm{cm}$인 것이다!) 매우 정밀하다고 할 수 있다. 단, 반올림을 수행할 시 정수 $m$에 대해 $(m+0.5)\times10^{-3}\mathrm{cm}$ 꼴의 키는 $(m+1)\times10^{-3}\mathrm{cm}$로 올림한다.

그저께 기계를 구매한 유림이는 그제와 어제 정오에 키를 측정해 보았다. 기계의 엄청난 정밀도에 힘입어, 실제로 키가 크는 것을 확인할 수 있었다! 유림이는 곧장 공책에 표를 하나 그린 뒤 앞으로 그곳에 전일 대비 성장을 기록하기로 하였다. 그제 측정된 키보다 어제 측정된 키가 $+0.006\mathrm{cm}$만큼 높았고, 유림이는 수치의 마지막 자리를 따 어제 날짜의 자리에 숫자 6을 적었다.

그런데 웬걸, 오늘의 전일 대비 성장 값이 $+0.007\mathrm{cm}$로 어제보다 높게 측정된 것이다! 유림이는 표의 다음 칸에 7을 적고는 신이 나서 자신의 성장률이 감소하지 않는다고 반 친구들에게 떠벌리고 다녔다. 하지만 이 자랑은 곧 전교 1등 동우의 귀에 들어갔고, 동우는 여기에 허점이 있음을 바로 파악해 냈다.

“만일 사흘 동안의 유림이 네 실제 키가 $140.0008\mathrm{cm}$, $140.0074\mathrm{cm}$, $140.0138\mathrm{cm}$였다 가정하면, 실제 전일 대비 성장은 $+0.0066\mathrm{cm}$에서 $+0.0064\mathrm{cm}$로 감소하였겠지만, 기계가 반올림하여 측정한 키는 각각 $140.001\mathrm{cm}$, $140.007\mathrm{cm}$, $140.014\mathrm{cm}$로, 네가 기록한 전일 대비 성장과 합치하는 결과를 얻게 되잖아! 그럼에도 네 성장률이 감소하지 않는다고 확신할 수 있어?” 동우가 반문했고, 유림이는 그냥 굳어 버렸다. 문제는 기계의 반올림에 있었다. 한 가지의 전일 대비 성장 데이터를 다양한 실제 성장이 설명할 수 있는데, 유림이는 이를 온전히 고려하지 않고 섣부른 결론을 내린 것이었다.

같은 날 저녁, 집에 도착한 유림이는 가만히 있을 수 없었다. 당장 오는 길에도 유림이의 친구들이 오늘 일을 갖고 놀려댔는데, 이대로라면 오늘 일이 자기 ‘흑역사’로 회자될 뿐만 아니라 자신이 성장률이 감소하는 아이라는 별명으로 낙인찍히는 것은 시간문제라 생각하였다.

유림이는 일단 전일 대비 성장 데이터와 이를 설명하는 실제 성장 사이의 관계를 자세히 파헤치며 전략을 세운 뒤, 한동안 키를 꾸준히 측정하며 전일 대비 성장 데이터를 만들어 반박하기로 하였다. 유림이의 전략 수립을 도와주자.

유림이는 연속한 $N$일 동안 전일 대비 성장을 기록한 다음, 실제 전일 대비 성장 값이 매일매일 감소하는 실제 성장 중 어느 것도 그 데이터를 설명할 수 없음을 보이는 전략을 짜냈다. 하지만 유림이는 이 전략이 영 달갑지 않았다. 주장에 반하는 실제 성장이 단 하나라도 존재하면 계획이 틀어져 버리니 이에 의존할 수 없던 것이다. 이에 유림이는 이번엔 전일 대비 성장 데이터를 설명하는 “상수 성장률 성장”을 하나 찾아 제시하는 전략을 짰다. 상수 성장률 성장이란, 시간에 따라 유림이의 키가 일정하게 증가하는 실제 성장 모형이다.

하지만 자신의 성장률이 진짜 감소할지도 모른다고 걱정한 유림이는 두 번째 전략마저도 신뢰할 수 없었다. 최후의 보루로, 유림이는 만일 전일 대비 성장 데이터가 상수 성장률 성장을 설명하지 못하면 어쩔 수 없이 몇 개의 값을 지워 강제로 설명하도록 만들기로 하였다. 여기서 값을 지운다는 것은 말 그대로 값을 없애고, 해당 값 좌우의 데이터를 이어 붙여 길이가 1 짧은 데이터를 형성한다는 의미이다(이 과정에서 데이터를 수집한 날짜의 연속성이 깨지게 되는데, 지워진 값 뒤의 모든 값에 대해 그 값을 기록한 날짜를 하루씩 앞당겨 고쳐 적음으로써 데이터가 다시 연속한 며칠 간의 전일 대비 성장 데이터가 되도록 한다).

연속한 $N$일 간의 전일 대비 성장 데이터가 주어질 때, 데이터 일부를 최소한만 지워서 그 데이터가 어떤 상수 성장률 성장을 설명하도록 만들어 보자.

첫 번째 줄에 정수 $N(1\leq N\leq 500)$이 주어진다.

두 번째 줄에 길이 $N$의 정수 수열의 항들이 공백을 구분으로 하여 순서대로 주어진다. 단, 각 항은 0 이상 10 미만의 정수이다.

주어진 수열의 각 항 $a$를 $+(0.001\times a)\mathrm{cm}$로 해석하여 만든 전일 대비 성장 데이터를 고려하자. 이 데이터가 어떤 상수 성장률 성장을 설명할 수 있도록 지워야 할 항의 최소 개수 $m$을 첫 줄에 출력한다.

$m>0$인 경우, $1$ 이상 $N$ 이하의 정수 중 ���치지 않게 $m$개를 골라, 두 번째 줄에 공백을 구분으로 하여 오름차순으로 출력한다. 두 번째 줄에 출력한 각각의 수 $k$마다 데이터의 $k$번째 항을 지워 만든 데이터는 한 상수 성장률 성장으로 설명될 수 있어야 한다.