Haybale Challenge

Farmer John's cows are hosting a programming contest for Farmer Nhoj's cows! In one of the problems, Haybales, you are given a non‐decreasing integer array \(x_1 \le x_2 \le \dotsb \le x_N\) and an unknown positive integer \(K\). Even though you do not know the array \(x\) or \(K\), you are given, for every index \(i\), the value \(j_i\) which is defined as the maximum index \(j\) (with \(i \le j \le N\)) such that

$$x_{j} \le x_i + K.$$

It is guaranteed that \(j_i\) satisfy \(i \le j_1 \le j_2 \le \cdots \le j_N \le N\) and that if \(j_i < N\) then

$$x_{j_i+1} > x_i + K.$$

Your task is to construct any non-decreasing array \(x\) of \(N\) integers along with an integer \(K\) so that:

• For all \(i\), \(0 \le x_i \le 10^{18}\).
• \(1 \le K \le 10^{18}\).
• The values \(j_1, j_2, \dots, j_N\) computed from \(x\) and \(K\) (using the rule above) match the given input.

One can prove that a solution always exists. Note that in any valid solution, the input \(j\)-sequence has a special structure: the indices can be partitioned into consecutive blocks such that every index in the same block gets the same \(j\)-value, equal to the last index of that block.

A simple valid solution is to choose \(K = 1\) and to construct \(x\) block by block. Suppose the first block covers indices \(1 \ldots r_1\) (so that for every index in that block, \(j_i = r_1\)). In that block we can set \(x_1 = x_2 = \cdots = x_{r_1} = 0\). If the next block covers indices \(r_1+1 \ldots r_2\), then we can set each \(x_i = 0 + (K+1) = 2\) in that block. More generally, if a block is the \(b^{th}\) block then assign all its entries the value \(2(b-1)\). This guarantees that for any index \(i\) in a block with constant value \(c\) (and block ending at \(r\)) we have:

• \(x_{r} = c \le c+1 = x_i + K\).
• If \(r c+1 = x_i + K\).

The input is given as follows.

inputFormat

The first line contains a single integer \(N\) (\(1 \le N \le 10^5\)).

The second line contains \(N\) space‐separated integers \(j_1, j_2, \dots, j_N\) (each between \(1\) and \(N\)) that satisfy \(i \le j_1 \le j_2 \le \cdots \le j_N \le N\). It is guaranteed that these numbers come from some valid array \(x\) and integer \(K\) as described in the problem statement. In particular, the \(j\)-sequence can be partitioned into consecutive blocks such that every index in the same block has the same \(j\)-value which is equal to the last index of that block.

outputFormat

Output two lines. The first line should contain \(N\) space-separated integers \(x_1, x_2, \dots, x_N\) (which must be non-decreasing and satisfy \(0 \le x_i \le 10^{18}\)). The second line should contain the chosen integer \(K\) (\(1 \le K \le 10^{18}\)).

sample

5
3 3 3 5 5

0 0 0 2 2
1

</p>