Mivik Convolution and Simple Polynomials

There once was a Mivik who loved convolution. He defined the Mivik convolution of two univariate polynomial functions \(f(x)\) and \(g(x)\) as follows:

[ f(x) \otimes g(x) = \sum_{k=0}^{\deg f + \deg g} \max_{\substack{0 \le i \le \deg f \ 0 \le j \le \deg g,; i+j=k}} \Big{ [x^i]f(x) + [x^j]g(x) \Big} , x^k ]

Here, \(\deg f\) denotes the degree of \(f(x)\) and \([x^i]f(x)\) denotes the coefficient of \(x^i\) in \(f(x)\). Note that the Mivik convolution is left associative, i.e. \[ a \otimes b \otimes c = (a \otimes b) \otimes c. \]

A Mivik function is defined as a polynomial of the form \(f(x)=ax+b\) with both \(a\) and \(b\) being integers. For example, \(f(x)=-3+2x\) is a Mivik function (but \(f(x)=\frac{1}{x}\) is not).

A polynomial \(f(x)\) is called simple if and only if there exists a sequence \(S\) of Mivik functions such that

[ f(x)=S_1 \otimes S_2 \otimes \cdots \otimes S_{|S|}. ]

One may show that if \(S_i(x)=a_ix+b_i\) and we define \(d_i = a_i-b_i\), then the convolution results in a polynomial whose coefficients are given by:

[ c_0 = B \quad \text{and} \quad c_k = B + \sum_{i=1}^{k} d_i \quad (1 \le k \le n), ]

where \(B = \sum_{i=1}^{n} b_i\) and \(n=|S|=\deg f\). In order for a polynomial \(f(x)=c_0+c_1x+\cdots+c_nx^n\) to be simple, the successive differences \(d_k=c_k-c_{k-1}\) (for \(1 \le k \le n\)) must satisfy

[ d_1 \ge d_2 \ge \cdots \ge d_n. ]

Your task is to determine whether a given polynomial \(f(x)\) (provided by its coefficients) is simple. If it is, you must also output one possible sequence \(S\) of Mivik functions whose convolution equals \(f(x)\). For the purpose of construction, if \(n\ge 1\) let:

• S₁(x) = \(c_1x+c_0\) (i.e. choose \(b_1=c_0\) and \(a_1=c_1\)).
• For \(2 \le i \le n\), choose S_i(x) = \((c_i-c_{i-1})x+0\).

If \(n=0\) (i.e. the polynomial is constant), consider it simple with an empty sequence.

inputFormat

The input consists of two lines:

• The first line contains a single integer \(n\) (\(0 \le n \le 10^5\)), representing the degree of the polynomial \(f(x)\).
• The second line contains \(n+1\) space-separated integers \(c_0, c_1, \ldots, c_n\), where \(c_i\) is the coefficient of \(x^i\) in \(f(x)\). It is guaranteed that \(|c_i| \le 10^9\).

outputFormat

If the polynomial is not simple, output a single line containing "NO".

If the polynomial is simple, output "YES" on the first line. On the next line, output an integer \(m\) denoting the number of Mivik functions in your sequence (note that when \(n=0\), output \(m=0\)). Then, for each of the \(m\) functions, output a line with two space-separated integers \(a\) and \(b\), representing the Mivik function \(S(x)=ax+b\).

Note: When \(m \ge 1\), a valid construction is as follows:

• Set \(S_1(x)=c_1x+c_0\) (thus \(a_1=c_1\) and \(b_1=c_0\)).
• For \(2 \le i \le n\), set \(S_i(x) = (c_i-c_{i-1})x+0\).

This construction works if and only if the differences \(d_i=c_i-c_{i-1}\) form a non-increasing sequence (i.e. \(d_1 \ge d_2 \ge \cdots \ge d_n\)).

sample

0
5

YES
0