Recollect Inequality

Given a sequence \(x\) of length \(n\), find a real number \(y\) such that for every pair of indices \(1\leq i |x_i - y|\) holds. In other words, if we define \(d_i = |x_i-y|\) then \(d_1, d_2, \ldots, d_n\) must be strictly increasing. If no such \(y\) exists, output "No solution".

Hint: For each adjacent pair \((x_i, x_{i+1})\), the inequality \(|x_{i+1} - y| > |x_i - y|\) can be transformed into:

• If \(x_{i+1} > x_i\): \(y < \frac{x_i+x_{i+1}}{2}\).
• If \(x_{i+1} \frac{x_i+x_{i+1}}{2}\).

If \(x_{i+1} = x_i\) for any \(i\), then no solution exists.

inputFormat

The first line contains a positive integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) space-separated numbers \(x_1, x_2, \ldots, x_n\).

outputFormat

If a valid real number \(y\) exists, output any such number. Otherwise, output "No solution".

sample

1
5

0