Math Quiz

Interview

Time limit1sMemory limit1024 MB

Summary

Given N integers A_k, find real p and q so that the sum of omega^A_k equals p*omega + q, where omega is a root of x^2 + x + 1 = 0.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

Eric wants to give a math quiz to KSA freshmen. To be precise, he wants the freshmen to reduce the number of terms in a math expression so that he can finish his own homework neatly.

Let $\omega$ be one complex root of the quadratic equation $x^2 + x + 1 = 0$ . Given $N$ integers $A_1, A_2, \cdots, A_N$ , find two real numbers $p$ and $q$ that satisfy the following equation.

$\sum_{k=1}^N \omega^{A_k} = \omega^{A_1} + \omega^{A_2} + \cdots + \omega^{A_N} = p\omega + q$

Solve this quiz on behalf of the KSA freshmen!

Input

The first line contains an integer $N$ .

The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ .

Output

Print the two real numbers $p$ and $q$ described in the problem. Answers with an absolute or relative error up to $10^{-9}$ are accepted.

Constraints

$2 \le N \le 3 \times 10^5$
$0 \le A_i \le 10^9$

Examples1

Example 1
Input
```
3
0 2 2
```
Expected output
```
-2.000000000 -1.000000000
```