use Collection.Generic;

class RecamanSequence {
  function : Main(args : String[]) ~ Nil {
    GenerateSequence();
  }

  function : native : GenerateSequence() ~ Nil {
    a := Vector->New()<IntHolder>;
    a->AddBack(0);

    used := Set->New()<IntHolder>;
    used->Insert(0);

    used1000 := Set->New()<IntHolder>;
    used1000->Insert(0);

    foundDup := false;
    n := 1;
    while (n <= 15 | <>foundDup | used1000->Size() < 1001) {
      next := a->Get(n - 1) - n;
      if (next < 1 | used->Has(next)) {
        next += 2 * n;
      };
      alreadyUsed := used->Has(next);
      a->AddBack(next);
      if (<>alreadyUsed) {
        used->Insert(next);
        if (0 <= next & next <= 1000) {
          used1000->Insert(next);
        };
      };
      if (n = 14) {
        str := ToString(a);
        "The first 15 terms of the Recaman sequence are : {$str}"->PrintLine();
      };
      if (<>foundDup & alreadyUsed) {
        "The first duplicate term is a[{$n}] := {$next}"->PrintLine();
        foundDup := true;
      };
      if (used1000->Size() = 1001) {
        "Terms up to a[{$n}] are needed to generate 0 to 1000"->PrintLine();
      };
      n++;
    };
  }

  function : ToString(a : Vector<IntHolder>) ~ String {
    out := "[";
    each(i : a) {
      out += a->Get(i)->Get();
      if(i + 1 < a->Size())  {
        out += ',';
      };
    };
    out += ']';

    return out;
  }
}