Dat je niz a celih brojeva dužine n. Pod transformacijom niza podrazumevamo povećavanje ili smanjivanje jednog elemenat niza za 1. Odrediti minimalni broj transformacija niza potrebnih da se on prevede u strogo rastući niz b. Za svaki element niza prikazati razliku: b[i] - a[i].

Ulaz:

(Ulazni podaci se nalaze u datoteci niz.in) U prvom redu se nalazi prirodni broj n (1 ≤ n ≤ 5.000) koji označava broj elemenata niza. U narednom redu se nalazi n celih brojeva koji predstavljaju elemente niza. Apsolutna vrednost elemenata nije veća od 1.000.000.000.

Izlaz:

(Izlazne podatke upisati u datoteku niz.out) U prvom redu treba ispisati minimalni broj transformacija potrebnih za dobijanje strogo rastućeg niza. U narednom redu štampati n brojeva odvojenih jednim razmakom koji predstavljaju promene brojeva početnog niza. Ukoliko promene nisu jedinstvene štampati bilo koju.

Primer 1:

4
1 1 1 1

4
-1 0 1 2

Primer 2:

5
1 1 1 6 4

5
-1 0 1 0 3

Objašnjenje.

U primeru 1 opisanim transformacijama bi dobili rastući niz b = 0, 1, 2, 3. U drugom primeru rešenje nije jedinstveno, npr. promene su mogle biti i: -1, 0, 1, -1, 2.

Napomena.

U 40% test primera apsolutna vrednost elemenata niza neće biti veća od 2.000.

/*
  Author: Andreja Ilic, PMF Nis
  e-mail: ilic_andrejko@yahoo.com
  Complexity: O(n^2)
*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include <algorithm>

using namespace std;
#define MAX_N 5005

int a [MAX_N], c [MAX_N], b [MAX_N], n, m, p [MAX_N][MAX_N], h [MAX_N];
long long d [MAX_N][MAX_N], sol;
FILE *in, *out;

    // Funkcija uporedjivanje za sortiranje
    int compare (const void * a, const void * b)
    {
        return (*(int*)a - *(int*)b );
    }

    // Inicijalizacija niza c = razlicite vrednosti elemenata
    // niza a, sortirani u rastucem poretku
    void initializationOfSteps()
    {
        for (int i = 0; i < n; i++)
        {
            c [i] = a [i];
        }
        sort(c, c + n);

    // izbacivanje istig vrednosti iz niza c
    // m = broj elemenata niza c
        m = 1;
        for (int i = 1; i < n; i++)
        {
            if (c [i] != c [i - 1])
            {
                c [m++] = c [i];
            }
        }
    }

    // Glavna metoda za racunanje resenja
    void solve()
    {
        // prebacivanje rada bez uslova stroge nejednakosti
        for (int i = 0; i < n; i++)
        {
            a [i] = a [i] - i;
        }

    // inicijalizacija mogucih vrednosti niza b
        initializationOfSteps();

        d [0][0] = abs (a [0] - c [0]);
        p [0][0] = 0;

        // Inicijalizacija prve kolone
        for (int i = 1; i < n; i++)
        {
            d [i][0] = d [i - 1][0] + abs (a [i] - c [0]);
            p [i][0] = 0;
        }

        // Inicijalizacija prve vrste
        for (int j = 1; j < m; j++)
        {
            if (abs (a [0] - c [j]) < d [0][j - 1])
            {
                d [0][j] = abs (a [0] - c [j]);
                p [0][j] = j;
            }
            else
            {
                d [0][j] = d [0][j - 1];
                p [0][j] = p [0][j - 1];
            }
        }

        // Inicijalizacija matrice d
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < m; j++)
            {
                if (d [i][j - 1] <= d [i - 1][j] + abs(a [i] - c [j]))
                {
          // u slucaju da niko od elemnata ne uzima vrednost c [j]
                    d [i][j] = d [i][j - 1];
                    p [i][j] = p [i][j - 1];
                }
                else
                {
          // u slucaju da element sa indeksom i uzima vrednost c [j]
                    d [i][j] = d [i - 1][j] + abs (a [i] - c [j]);
                    p [i][j] = j;
                }
            }
        }

        // Racunanje minimalnog broja transformacija
        sol = d [n - 1][m - 1];
    // currentIndex = index vrednosti elementa, preko niza c
        int currentIndex = p [n - 1][m - 1];
        for (int j = m - 2; j >= 0; j--)
        {
            if (sol > d [n - 1][j])
            {
                sol = d [n - 1][j];
                currentIndex = p [n - 1][j];
            }
        }

        // Nalazenje pomeraja za svaki element
        for (int i = n - 1; i >= 0; i--)
        {
            b [i] = c [currentIndex];
            if (i == 0)
                break;
            int lastIndex = currentIndex;
      // updatovanje currentIndex-a
            int currentMin = d [i - 1][currentIndex];
            currentIndex = p [i - 1][currentIndex];
            for (int j = lastIndex - 1; j >= 0; j--)
            {
                if (currentMin > d [i - 1][j])
                {
                    currentMin = d [i - 1][j];
                    currentIndex = p [i - 1][j];
                }
            }
        }
    }

    // Unos podataka
    void input()
    {
        in = fopen ("niz.in", "r");
        fscanf (in, "%d", &n);
        for (int i = 0; i < n; i++)
        {
            fscanf (in, "%d", &a [i]);
        }
        fclose(in);
    }

    // Ispis resenja
    void output()
    {
        out = fopen ("niz.out", "w");
        fprintf (out, "%lld\n", sol);
        for (int i = 0; i < n; i++)
            fprintf (out, "%d ", (b [i] - a [i]));
        fprintf(out, "\n");
        fclose(out);
    }

    int main()
    {
        input();
        solve();
        output();

        return 0;
    }