Background

Recently, are you busy? You did not even call me. Oh, really? Hehe, turns out I never gave you my number. But still, that is not an excuse for you not to look for me. Next time, I will punish you to keep me company until the sun comes up. —— recollect_i's blog.

Problem Description

recollect_i gives you a sequence $x$ of length $n$. You need to find a real number $y$ such that for all $1\leq i<j\leq n$, $\vert x_j-y\vert>\vert x_i-y\vert$, or report that there is no solution.

Input Format

The first line contains an integer $n$, representing the length of the sequence.

The second line contains $n$ integers $x$, representing the sequence.

Output Format

If there is a solution, output the string lovely on the first line, and output a real number $y$ on the second line.

To avoid precision issues, if your output satisfies that for all $1\leq i<j\leq n$, $\vert x_j-y\vert-\vert x_i-y\vert>10^{-6}$, then your answer is considered correct.

You also need to ensure that $-2\times 10^9\leq y\leq 2\times 10^9$, and that $y$ has no more than $10$ digits after the decimal point. Otherwise, the correctness of judging cannot be guaranteed.

If there is no solution, output the string pigeon in one line.

5
1 2 3 4 5

lovely
-114514

5
3 2 1 6 7

lovely
3.1416

5
3 2 1 4 5

pigeon

Hint

[Hint]

In the output format, $>10^{-6}$ is only to avoid precision issues. You may treat it as requiring $\vert x_j-y\vert>\vert x_i-y\vert$.

It can be proven that if there is a solution, then there must exist a $y$ satisfying $-2\times 10^{9}\leq y\leq2\times 10^{9}$ and for all $1\leq i<j\leq n$, $\vert x_j-y\vert-\vert x_i-y\vert>0.2$, and the number of digits after the decimal point does not exceed $3$.

[Constraints]

For all testdata: $5\leq n\leq10^5$, $-10^9\leq x_i\leq10^9$.

Translated by ChatGPT 5