最近的TOI流行先解釋一個數學概念後再要求大家實作。

為了跟進潮流，今天我們要來看的主題是，代數體的擴張及其應用。

下面主要要證明的是複數域\(\mathbb{C}\)是代數封閉域，也就是我們熟悉的代數基本定理。

首先我們需要兩個引理，第一個是奇數次實係數多項式一定有一個複數根，而這可以由中間值定理得到，或是高中的勘根定理。

第二個引理是二次多項式一定有整數解，我們熟知的二次方程公式解可以直接由配方構造出兩個根，所以這也是對的。

接著我們要證明每個實係數多項式都有一個複數根

設 \(g(x)\in \mathbb{R}[x]\)，\(\deg g(x) = d\ge 1\)。令 \(n = v_2(d)\)，也就是最大的 \(n\) 使得 \(\frac{d}{2^n}\) 是整數。

對 \(n\) 進行數學歸納法，奠基當 \(n = 0\) 時， \(g(x)\) ?是奇次實係數多項式，已經被證明有根。下面假設 \(n = n_0-1\) 時成立並考慮 \(n = n_0\) 的情況。

假設 \(x_1,x_2,...x_d\) 是 \(g(x)\) 在某個 \(\mathbb{R}\) 擴域下的所有根。那麼所求即要證明，某個 \(x_i\in \mathbb{C}\)。

現在任取一個實數 \(c\) ， 令 \(y_{ij} = x_i + x_j + cx_ix_j\) ，\(1\le i\le j\le d\)，所以一共有 \(\frac{d(d+1)}{2}\)個 \(y_{ij}\)，注意到 \(v_2(\frac{d(d+1)}{2}) = n-1\)。

再令 \(G(x) = \prod_{1\le i\le j\le d} (x - y_{ij}) = x^m + g_1(x_1,x_2,...,x_d)x^{m-1} + ... + g_m(x_1,x_2,...,x_d)\)

其中每個 \(g_i(x_1,x_2,...,x_d)\) 都是 \(x_1,x_2,...,x_d\) 的對稱多項式，意即 \(g_i(x_1,x_2,...,x_d) = g_i(x_{p(1)},x_{p(2)},...,x_{p(d)})\)，對於任意 \(1～d\) 的排列 \(p(1),p(2),...,p(d)\)。

於是 \(g_i\) 是初等對稱多項式的實係數多項式組合。然而我們知道，由根與係數關係知，所有關於 \(x_1,x_2,...,x_d\) 的初等多項式都是 \(g\) 的係數，從而他們都是實數，也就表明了 \(g_i\) 也是實數。

因此 \(G\) 是實係數多項式，又前面說到 \(v_2(\deg G) = n-1\)，由歸納假設知 \(G\) 有複數根 \(z_0\)。這代表了有某組 \(i,j\) 滿足 \(x_i + x_j + cx_ix_j = z_0\)。

最初我們的實數參數 \(c\) 並沒有被限定，當我們取 \(\deg G+1\) 個不同的 \(c\) 之後，由鴿籠原理知會有兩個不同的參數給出一樣的 \(i,j\)。假設 \(x_i+x_j+ux_ix_j = z_1\) 和 \(x_i+x_j+vx_ix_j = z_2\)。

在這裡解二元一次方程式容易得出 \(x_i+x_j\in \mathbb{C}\)，\(x_ix_j\in \mathbb{C}\)。那麼就有 \(x^2-(x_i+x_j)x+x_ix_j\in \mathbb{C[x]}\)，且這個二次方程的兩根是\(x_i,x_j\)。

前面說到，一個複係數二次多項式一定有複數根，所以某個 \(x_i,x_j\) 一定是複數，所求得證。

到這裡幾乎完成代數基本定理的證明， \(n\)次實係數多項式一定有一個複數根，注意到由數學歸納法容易推論出 \(n\) 次實係數多項式恰有 \(n\) 個複數根，如果計算重數。本題題目內容即為給一個多項式，問有幾個複數根。下面繼續完成證明。

對於一個複係數多項式 \(f(x)\)。由複數的性質，容易驗得 \(f(x)\bar f(x)\in \mathbb{R}[x]\)，由前面的結果知道 \(f(x)\bar f(x)\) 有一個複數根 \(\alpha\)。

如果 \(\alpha\) 是 \(f(x)\) 的根，那 \(f(x)\) 就有複數根了，否則 \(\alpha\) 是 \(\bar f(x)\) 的根，那麼 \(\bar \alpha\) 是 \(f(x)\) 的根，因此代數基本定理得證。

儘管代數基本定理的代數證明繁瑣，他在別的領域有各種相對簡單的證明，例如複分析

假設 \(p(z)\) 是多項式沒有複數根，那麼 \(\lim_{z\rightarrow \infty}\frac{1}{p(z)}\rightarrow 0\)，所以 \(\frac{1}{|p(z)|}\)有界。由Liouville定理知，\(\frac{1}{p(x)}\)是常數，矛盾。

最近防疫期間，大家要記得多洗手喔！

參考資料：代數數論入門(馮克勤，2015); Complex Analysis, 洗手歌(Frederick Fong, 2020)

Input

第一行一個數字 \(n\)

\(0\le n\le 10^5\)

接下來 \(n+1\) 個數字， \(a_0,a_1,...,a_n\)，代表多項式係數\(a_0+a_1x+a_2x^2+...+a_nx^n\)

\(-10^9\le a_0,a_1,...,a_n\le 10^9\)

Output

輸出這個多項式有幾個複數根，如果無限多個則輸出 \(-1\)。

Constraints

第 \(1\) 組測資, \(n = 0\)。 \((20\text{%})\)

第 \(2\) 組測資, \(n = 1\)。\((20\text{%})\)

第 \(3\) 組測資, \(a_n\ne 0\)。\((20\text{%})\)

第 \(4\) 組測資, \(n\le 100\)。\((20\text{%})\)

第 \(5\) 組測資, 沒有其他限制。\((20\text{%})\)

Sample Input

3
1 2 3 4

Sample Output

3