Smooth numbers

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

요약

자릿수 l(최대 100)이 주어질 때, 양 끝을 제외한 모든 자릿수가 양옆 자릿수의 평균보다 작은 l자리 수 중 가장 큰 수를 구하거나, 없으면 -1을 출력합니다.

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

문제

Let's call positive integer smooth if each of its digits except the first and the last is less then the average of it's two neighbor digits. It means that if $x = a\_n \cdot 10^n + a\_{n-1} \cdot 10^{n-1} + ... + a\_1 \cdot 10 + a\_0$ then for each $i = 1 ... {n-1}$ the inequality $a\_i < (a\_{i - 1} + a\_{i + 1}) / 2$ holds.

Vasya has been studying smooth numbers for a long time and he wants to know, if any smooth number of exactly $l$ digits exists, and if so, what is the greatest $l$ -digit smooth number.

Vasya is asking you for help! Find the greatest $l$ -digit smooth number.

출력

Input file contains the only integer $l$ ( $1 \le l \le 100$ ) --- number of digits in smooth number.

제한

Output the greatest $l$ -digit smooth number or $-1$ if it does not exist.

예제1

예제 1
입력
```
3
```
예상 출력
```
989
```