Có \(n\) con kiến trên một sợi dây. Chúng được đánh số thứ tự từ \(1\) đến \(n\). Quy ước tọa độ của sợi dây là một trục \(Ox\) với hai đầu mút là \(-10^9\) và \(10^9\). Ban đầu các con kiến đứng tại tọa độ \(a_1, a_2, ..., a_n\). Mỗi giây, mỗi con kiến có thể bò sang trái \(1\) đơn vị, sang phải \(1\) đơn vị, hoặc đứng yên. Nói cách khác, sau mỗi giây, \(a_i=a_i + 1, a_i - 1\) hoặc \(a_i\).

Kiến Vua rất không hài lòng vì thứ tự các con kiến đứng rất lộn xộn, vì vậy ông muốn chúng di chuyển về lại trật tự để dễ quản lý. Ông muốn con kiến thứ nhất đứng bên trái con thứ hai, con thứ hai đứng bên trái con thứ ba, ... Hay nói cách khác, \(a_1 < a_2 < ... < a_n\).

Hỏi cần ít nhất bao nhiêu giây để các con kiến tạo thành trật tự như nhà vua mong muốn nếu chúng di chuyển một cách tối ưu? Biết rằng nhà vua chỉ kiểm tra trật tự tại các thời điểm là số nguyên. Giả sử sợi dây đủ rộng để các con kiến không bị rơi xuống đất khi gặp nhau.

Input

• Dòng đầu chứ một số nguyên dương \(n\) là số lượng kiến trên dây.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n \ (-10^8 \leq a_i \leq 10^8)\) là tọa độ ban đầu của các con kiến.

Output

• Dòng đầu in ra một số nguyên dương là thời gian ít nhất để các con kiến di chuyển và tạo thành trật tự nhà vua mong muốn.

• Dòng thứ hai in ra \(n\) số nguyên \(b_1, b_2, ..., b_n \ (-10^9 \leq b_i \leq 10^9)\) là tọa độ của các con kiến sau khi di chuyển xong.

• Lưu ý:

• Nếu in đúng đáp án dòng 1, bạn sẽ được \(50\%\) số điểm của test tương ứng.
• Nếu có nhiều phương án cho dòng 2, bạn chỉ cần in một đáp án bất kỳ

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \leq 3000\).
• Subtask \(2\) (\(60\%\) số điểm): \(n \leq 3 \times 10^5\).

Example

3
3 2 1

2
1 2 3

4
1 2 3 4

0
1 2 3 4