Smooth numbers

Interview

Time limit2sMemory limit1024 MB

Summary

Given a digit count l (1 to 100), find the largest l-digit number whose interior digits are each less than the average of their neighbors, or report -1.

Level: Medium5 of 10
Topics: Math, Greedy, Brute force
Solved: No attempts yet

Problem

A positive integer is called smooth if each of its digits except the first and the last is less than the average of its two neighboring digits. That is, if $x = a_n \cdot 10^n + a_{n-1} \cdot 10^{n-1} + \cdots + a_1 \cdot 10 + a_0$ , then $a_i < \frac{a_{i-1} + a_{i+1}}{2}$ for every $i$ with $1 \le i \le n-1$ .

Vasya has studied smooth numbers for a long time. He wants to know whether a smooth number with exactly $l$ digits exists and, if one does, what the greatest such number is. Help Vasya find the greatest $l$ -digit smooth number.

Input

The input file contains one integer $l$ ( $1 \le l \le 100$ ), the number of digits in the smooth number.

Output

Print the greatest $l$ -digit smooth number, or $-1$ if no such number exists.

Examples1

Example 1
Input
```
3
```
Expected output
```
989
```