감소하는 성장률의 비극 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을 출력한다.