Problem Background

Recently, busy? Haven't called. Oh, is that so? Hehe, I never gave you my number. But this, is not, a reason for you not to look for me. Next time, I'll punish you to wait with me until the sun rises. ——recollect_i's blog

Problem Description

recollect_i has given 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, the first line should output the string lovely, and the second line should output a real number \( y \).

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

You also need to ensure \( -2 \times 10^9 \leq y \leq 2 \times 10^9 \), and \( y \) should have no more than 10 decimal places, otherwise, the correctness of the evaluation cannot be guaranteed.

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

Sample Input and Output

Sample Input #1

5
1 2 3 4 5

Sample Output #1

lovely
-114514

Sample Input #2

5
3 2 1 6 7

Sample Output #2

lovely
3.1416

Sample Input #3

5
3 2 1 4 5

Sample Output #3

pigeon

Notes

Hints

The condition \( > 10^{-6} \) in the output format is just to avoid precision issues. You can consider it as requiring \( \vert x_j - y \vert > \vert x_i - y \vert \).

It can be proven that if there is a solution, there must exist a \( y \) satisfying \( -2 \times 10^9 \leq y \leq 2 \times 10^9 \) and for all \( 1 \leq i < j \leq n \), \( \vert x_j - y \vert - \vert x_i - y \vert > 0.2 \), with no more than 3 decimal places.

Data Range

For all data, it is guaranteed that \( 5 \leq n \leq 10^5 \) and \( -10^9 \leq x_i \leq 10^9 \).

见题面 Input 部分

见题面 Output 部分