#USACOC2222C. Tests for Haybales

Tests for Haybales

Description

Farmer John's cows have decided to offer a programming contest for the cows onFarmer Nhoj's farm. In order to make the problems as fun as possible, they havespent considerable time coming up with challenging input cases. For one problemin particular, "Haybales", the cows need your help devising challenging inputs. This involve solving the following somewhat intriguing problem:

There is an array of sorted integers x1x2xNx_1 \leq x_2 \leq \dotsb \leq x_N, and an integer KK. You don't know the array or KK, butyou do know for each index ii, the largest index jij_i such that xjixi+Kx_{j_i} \leq x_i + K. It is guaranteed that ijii\le j_i and j1j2jNNj_1\le j_2\le \cdots \le j_N\le N.

Given this information, Farmer John's cows need to construct any array along with some integer KK that matches that information. The construction needs tosatisfy 0xi10180 \leq x_i \leq 10^{18} for all ii and 1K10181 \leq K \leq 10^{18}.

It can be proven that this is always possible. Help Farmer John's cows solvethis problem!

  • 1N1051 \leq N \leq 10^5

Input Format

The first line of input contains NN. The next line contains j1,j2,,jNj_1,j_2,\ldots,j_N.

Output Format

Print KK, then x1,,xNx_1,\ldots,x_N on separate lines. Any valid output will be accepted.

6
2 2 4 5 6 6
6
2 2 4 5 6 6

Scoring

  • For 50% of all inputs, N5000N\le 5000
  • For the remaining inputs, there are no additional constraints.

Problem Credit

Problem credits: Danny Mittal