28684번 - 감소하는 성장률의 비극 1

문제

유림이는 자신의 성장률이 감소한다는 점을 느끼고 매우 슬펐다. 그러던 어느 날, 유림이는 우연히 키를 매우 정밀하게 측정해 주는 비싼 기계에 눈독을 들여 이를 구입하게 되었다. 이 기계는 유림이의 키를 반올림하여 $\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$일 동안 전일 대비 성장을 기록한 다음, 실제 전일 대비 성장 값이 매일매일 감소하는(단조 감소다. 즉, 성장 값이 일정한 구간이 간혹 있더라도 감소가 맞는 것으로 본다) 실제 성장 중 어느 것도 그 데이터를 설명할 수 없음을 보이는 전략을 짜냈다.

연속한 $N$일 간의 전일 대비 성장 데이터가 주어질 때, 이것이 가능한지를 판별하여 보자.

입력

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

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

출력

주어진 수열의 각 항 $a$를 $+(0.001\times a)\mathrm{cm}$로 해석하여 만든 전일 대비 성장 데이터를 고려할 때, 실제 전일 대비 성장이 매일 감소하는 어떤 실제 성장도 이 데이터를 설명할 수 없다면 Provable을, 그렇지 않다면(그러한 실제 성장이 존재한다면) Not Provable을 출력한다.

제한

힌트