/**
 * @copyright (c) 2020 Daisuke Hashimoto
 */


#include <cstdint>
#include <iostream>

constexpr int32_t kMaxArraySize = 1000000;

class ShellSort {
 public:
  ShellSort() noexcept;
  ~ShellSort() noexcept;
  void Main(std::istream &input_stream) noexcept;

 private:
  void Sort() noexcept;
  void InsertionSort(const int32_t gap) noexcept;
  void SwapAndInsert(const int32_t index_source, const int32_t gap) noexcept;
  bool ShouldSwap(const int32_t index_compare, const int32_t cvalue) noexcept;
  int32_t SwapAndGetInsertPoint(const int32_t index_compare, const int32_t gap) noexcept;
  void Insert(const int32_t index_insert_target, const int32_t cvalue) noexcept;
  void Load(std::istream &input_stream);
  void Print() const noexcept;
  void CalculateGaps() noexcept;

 private:
  ShellSort(const ShellSort &obj) noexcept = delete;
  ShellSort &operator=(const ShellSort &obj) noexcept = delete;
  ShellSort(ShellSort &&obj) = delete;
  ShellSort &operator=(ShellSort &&obj) = delete;

 private:
  int32_t count_;
  int64_t swap_count_;
  int32_t number_of_gaps_;
  int32_t gaps_[100];
  int32_t values_[kMaxArraySize];
};

ShellSort::ShellSort() noexcept : count_(0), swap_count_(0), number_of_gaps_(0), gaps_{-1}, values_{-1} {}

ShellSort::~ShellSort() noexcept {}

void ShellSort::Main(std::istream &input_stream) noexcept {
  try {
    Load(input_stream);
    Sort();
    Print();
  } catch (...) {
    std::cout << "ERROR" << std::endl;
  }
}

void ShellSort::Sort() noexcept {
  CalculateGaps();
  for (int32_t index = number_of_gaps_ - 1; index >= 0; --index) {
    InsertionSort(gaps_[index]);
  }
}

void ShellSort::CalculateGaps() noexcept {
  gaps_[0] = 1;
  for (number_of_gaps_ = 1; number_of_gaps_ <= 100; ++number_of_gaps_) {
    gaps_[number_of_gaps_] = 3 * gaps_[number_of_gaps_ - 1] + 1;
    if (gaps_[number_of_gaps_] > count_) {
      break;
    }
  }
}

void ShellSort::InsertionSort(const int32_t gap) noexcept {
  for (int32_t index_source = gap; index_source < count_; ++index_source) {
    SwapAndInsert(index_source, gap);
  }
}

void ShellSort::SwapAndInsert(const int32_t index_source, const int32_t gap) noexcept {
  int32_t cvalue = values_[index_source];
  int32_t index_insert_target = index_source;
  for (int32_t index_compare = index_source - gap; index_compare >= 0; index_compare -= gap) {
    if (ShouldSwap(index_compare, cvalue)) {
      index_insert_target = SwapAndGetInsertPoint(index_compare, gap);
    } else {
      break;
    }
  }
  Insert(index_insert_target, cvalue);
}

bool ShellSort::ShouldSwap(const int32_t index_compare, const int32_t cvalue) noexcept {
  return (values_[index_compare] > cvalue);
}

int32_t ShellSort::SwapAndGetInsertPoint(const int32_t index_compare, const int32_t gap) noexcept {
  values_[index_compare + gap] = values_[index_compare];
  const int32_t index_insert_target = index_compare;
  ++swap_count_;
  return index_insert_target;
}

void ShellSort::Insert(const int32_t index_insert_target, const int32_t cvalue) noexcept {
  values_[index_insert_target] = cvalue;
}

void ShellSort::Load(std::istream &input_stream) {
  input_stream >> count_;
  if (count_ > kMaxArraySize) {
    std::cout << "kMaxArraySize is too small for the number of data count." << std::endl;
    throw 1;
  }
  for (int32_t index = 0; index < count_; ++index) {
    input_stream >> values_[index];
  }
}

void ShellSort::Print() const noexcept {
  std::cout << number_of_gaps_ << std::endl;
  for (int32_t index = number_of_gaps_ - 1; index >= 0; --index) {
    if (index != number_of_gaps_ - 1) {
      std::cout << " ";
    }
    std::cout << gaps_[index];
  }
  std::cout << std::endl;
  std::cout << swap_count_ << std::endl;
  for (int32_t index = 0; index < count_; ++index) {
    std::cout << values_[index] << std::endl;
  }
}


int main(int argc, char *argv[]) {
  ShellSort *shell_sort = new ShellSort();
  shell_sort->Main(std::cin);
  delete shell_sort;
  return 0;
}



Measured memory_bytes: 6696