Za prirodan broj kažemo da je lep ukoliko je u njemu rastojanje između svake dve iste cifre bar 10. Rastojanje između dve cifre jednako je broju cifara između njih + 1 (recimo, u broju 12342, rastojanje između cifara '2' je 3).

Imamo početni broj od n cifara i želimo da od njega napravimo lep broj. U jednom potezu moguće je obrisati bilo koju cifru početnog broja i na njeno mesto upisati neku drugu cifru. Koliko je najmanje poteza potrebno da bi dobili lep broj?

Ulaz.

(Ulazni podaci se uqitavaju iz datoteke lepbroj.in) U prvom redu ulazne datoteke nalazi se jedan prirodan broj n koji predstavlja broj cifara početnog broja (1 ≤ n ≤ 10⁶). U sledećem redu se nalazi početni broj. Između cifara ne postoji razmak i broj može imati vodeće nule.

Izlaz.

(Izlazni podaci se ispisuju u datoteku lepbroj.out) U prvom i jedinom redu izlazne datoteke ispisati najmanji broj poteza potrebnih da se od datog broja dobije lep broj.

Primer 1.

8
00346731

2

Objašnjenje. Ukoliko obrišemo cifru 0 na drugoj poziciji i umesto nje napišemo cifru 2 i obrišemo cifru 3 na sedmoj poziciji i napišemo cifru 5, dobijamo lep broj 02346751. Moguće je dobiti i druge lepe brojeve ali ne u manjem broju poteza.

#include <cstdlib>
#include <cstdio>
#include <memory>

const int MaxN = 1000010;

char s[MaxN];
int m[12][12];
int p[12];
bool mark[12];
int n, sol;

void compareSolution()
{
  int curr = 0;
  for (int i = 0; i < 10; i++)
    curr += m[ p[i] ][i];

  if (curr < sol) 
    sol = curr;
}

void permutations(int k)
{
  if (k >= 10)
  {
    compareSolution();
  }
  else
  {
    for (int i = 0; i < 10; i++)
      if (!mark[i])
      {
        p[k] = i;
        mark[i] = true;
        permutations(k + 1);
        mark[i] = false;
      }
  }
}

int main()
{
  FILE* inFile = fopen("lepbroj.in", "r");
  FILE* outFile = fopen("lepbroj.out", "w");

  fscanf(inFile, "%d", &n);
  fscanf(inFile, "%s", s);

  memset(m, 0, sizeof(m));
  for (int i = 0; i < n; i++)
    m[s[i] - '0'][i % 10]++;

  for (int i = 0; i < 10; i++)
    for (int j = 0; j < 10; j++)
    {
      m[i][j] = (n / 10) - m[i][j];
      if (1 <= j + 1 && j + 1 <= n % 10) m[i][j]++;
    }

  sol = n + 1;
  memset(mark, false, sizeof(mark));
  permutations(0);

  fprintf(outFile, "%d\n", sol);

  fclose(inFile);
  fclose(outFile);

  return 0;
}

const
  MaxN = 1000010;

var
        inFile, outFile : text;
  n, i, j, curr, sol : longint;
  m : array[0..12, 0..12] of longint;
  p : array[0..12] of longint;
  mark : array[0..12] of boolean;
        c : char;

procedure compareSolution;
begin
  curr := 0;
  for i := 0 to 9 do
    curr := curr + m[ p[i] ][i];

  if (curr < sol) then sol := curr;
end;

procedure permutations(k : longint);
var
  i : longint;
begin
  if (k >= 10) then compareSolution
  else
    for i := 0 to 9 do
      if (NOT mark[i]) then
      begin
        p[k] := i;
        mark[i] := true;
        permutations(k + 1);
        mark[i] := false;
      end;
end;

BEGIN

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

  fillchar(m, sizeof(m), 0);

  readln(inFile, n);
  for i := 1 to n do
  begin
    read(inFile, c);
    m[ord(c) - 48][i mod 10] := m[ord(c) - 48][i mod 10] + 1;
  end;

  for i := 0 to 9 do
    for j := 0 to 9 do
    begin
      m[i][j] := (n div 10) - m[i][j];
      if ((1 <= j + 1) and (j + 1 <= n mod 10)) then
        m[i][j] := m[i][j] + 1;
    end;

  sol := n + 1;
  fillchar(mark, sizeof(mark), false);
  permutations(0);

  writeln(outFile, sol);

  close(inFile);
  close(outFile);

END.