This problem is a programming version of Problem 206 from projecteuler.net
Find the unique positive integer whose square's decimal representation has the form
where are known single digits and are unknown single digits.
In other words, find the unique positive integer when given the every other digit of its square, starting with the first digit and including the last digit of the square.
Input Format
The first line contains a single positive integer denoting the number of the known digits.
The second line contains the list of single-space separated known digits.
It is guaranteed that the answer exists and it is unique.
Constraints
- as the number of known digits;
- The first known digit cannot be zero.
Output Format
On a single line print the answer.
Sample Input 0
3
8 7 6
Sample Output 0
286
Explanation 0
We need to find a positive integer whose square has the form where each is a single unknown digit. It is easy to validate that
Therefore the answer is .
Sample Input 1
4
1 2 3 4
Sample Output 1
1312
Explanation 1
We are looking for a positive integer whose square has the form . Given the total number of the digits in the square, we can speculate that the answer is an integer less than . Exhaustive search shows that
Therefore the answer is .