Mika igra jednu, ne tako poznatu, kockarsku igru žetoni. Igra se sastoji u sledećem: na početku, ispred njega se nalazi n gomila žetona u nizu, pri čemu je na i-toj gomili a_i žetona. Zatim Mika odigra određeni broj poteza, gde se pod jednim potezom podrazumeva izbor dva broja i i j (i ≤ j) i dodavanje po jednog žetona svim gomilama između i-te i j-te, uključujući i ove dve gomile. Cilj igre je da, posle nekog broja poteza, na svim gomilama bude tačno k žetona.

Kada se igra završi, igrač dobija žetone na osnovu broja odigranih poteza - šo manje poteza, to više žetona. Odredite koliko je najmanje poteza potrebno da bi Mika završio igru i možda ćete dobiti neke od Mikinih žetona.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke zetoni.in.) U prvom redu ulazne datoteke nalaze se dva prirodna broja, n i k, koji predstavljaju, redom, broj gomila i traženi broj žetona na svakoj gomili na kraju igre (1 ≤ n ≤ 10⁶, 1 ≤ k ≤ 10⁹). U narednom redu nalaze se n celih brojeva iz segmenta [0, k] - opis gomila.

Izlaz.

(Izlazni podaci se ispisuju u datoteku zetoni.out) U prvom i jedinom redu izlazne datoteke ispisati jedan ceo broj - najmanji broj poteza potrebnih da se završi igra. Koristiti 64-bitni tip podataka.

Primer 1.

4 5
2 1 3 1

6

Objašnjenje.Ukoliko sa [i, j] označimo dodavanje po jednog žetona gomilama i, i + 1, ..., j, onda nizom od 6 poteza [2, 4], [4, 4], [4, 4], [1, 4], [1, 2], [1, 2] dobijamo po 5 žetona na svakoj gomili, kao što je i trebalo. Ovo nije moguće postići u manje od 6 poteza.

Napomena.
U 30% test primera je n ≤ 10³.

#include <cstdlib>
#include <cstdio>
#include <ctime>

const int MaxN = 1000100;

struct CoinPile
{
  int num, left, right;

  CoinPile(int n, int l, int r)
  {
    num = n; left = l; right = r;
  }
  CoinPile() {}
};

int n, k, x, pileNum, currIndex, nextIndex;
long long sol;
CoinPile coins[MaxN];

int main() 
{
  freopen("zetoni.in", "r", stdin);
  freopen("zetoni.out", "w", stdout);

  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++)
  {
    scanf("%d", &x);
    coins[i] = CoinPile(x, i - 1, i + 1);
  }
  coins[0] = CoinPile(k + 1, 0, 1);
  coins[n + 1] = CoinPile(k + 1, n, n + 1);

  sol = -1;
  currIndex = 1;
  pileNum = n + 2;
  while (pileNum > 2)
  {
    if (coins[ coins[currIndex].left ].num <= coins[ coins[currIndex].right ].num)
      nextIndex = coins[currIndex].left;
    else
      nextIndex = coins[currIndex].right;

    if (coins[nextIndex].num >= coins[currIndex].num)
    {
      sol += (coins[nextIndex].num - coins[currIndex].num);
      pileNum--;
      coins[ coins[currIndex].left ].right = coins[currIndex].right;
      coins[ coins[currIndex].right ].left = coins[currIndex].left;
    }

    currIndex = nextIndex;
  }

  printf("%lld\n", sol);
  return 0;
}

const
  MaxN = 1000100;

var
  inFile, outFile : text;
  n, k, x, pileNum, currIndex, nextIndex, i : longint;
  sol : int64;
  num, left, right : array[0..MaxN] of longint;

BEGIN
  
  assign(inFile, 'zetoni.in');
  assign(outFile, 'zetoni.out');
  reset(inFile); rewrite(outFile);

  read(inFile, n, k);
  for i := 1 to n do begin
    read(inFile, num[i]);
    left[i] := i - 1;
    right[i] := i + 1;
  end;
  
  num[0] := k + 1; left[0] := 0; right[0] := 1;
  num[n + 1] := k + 1; left[n + 1] := n; right[n + 1] := n + 1;

  sol := -1;
  currIndex := 1;
  pileNum := n + 2;
  while (pileNum > 2) do begin
  
    if (num[ left[currIndex] ] <= num[ right[currIndex] ]) then
      nextIndex := left[currIndex]
    else
      nextIndex := right[currIndex];

    if (num[nextIndex] >= num[currIndex]) then begin
    
      sol := sol + (num[nextIndex] - num[currIndex]);
      pileNum := pileNum - 1;
      right[ left[currIndex] ] := right[currIndex];
      left[ right[currIndex] ] := left[currIndex];

    end;

    currIndex := nextIndex;
    
  end;

  writeln(outFile, sol);
  close(inFile);
  close(outFile);
  
END.