description: Let's call a set of positive integers a_1, a_2, ..., a_k quadratic if the product of the factorials of its elements is a square of an integer, i. e. ∏_{i=1}^{k} a_i! = m^2, for some integer m.
  
  You are given a positive integer n.
  
  Your task is to find a quadratic subset of a set 1, 2, ..., n of maximum size. If there are multiple answers, print any of them.
  
  Input
  
  A single line contains a single integer n (1 ≤ n ≤ 10^6).
  
  Output
  
  In the first line, print a single integer — the size of the maximum subset. In the second line, print the subset itself in an arbitrary order.
  
  Examples
  
  Input
  
  
  1
  
  
  Output
  
  
  1
  1 
  
  
  Input
  
  
  4
  
  
  Output
  
  
  3
  1 3 4 
  
  
  Input
  
  
  7
  
  
  Output
  
  
  4
  1 4 5 6 
  
  
  Input
  
  
  9
  
  
  Output
  
  
  7
  1 2 4 5 6 7 9 
solution: #include <bits/stdc++.h>
  using namespace std;
  bool is_perfect_square(unsigned long long int n) {
    if (pow((long int)(sqrt(n)), 2) == n) {
      return true;
    }
    return false;
  }
  void solve() {
    unsigned long int n;
    cin >> n;
    vector<unsigned long int> arr = {};
    unsigned long int halfi = (long int)n / 2;
    unsigned long long int asdf =
        (unsigned long long int)2 * (halfi) * (halfi - 1);
    if ((n % 4) == 0) {
      arr = {halfi};
    } else if (n == 1) {
      arr = {};
    } else if (n % 4 == 1) {
      arr = {halfi, n};
    } else if ((n % 4) == 2) {
      if (is_perfect_square((unsigned long long int)(n + 2)))
        arr = {halfi + 1};
      else if (is_perfect_square((unsigned long long int)(n * (halfi - 1))))
        arr = {halfi - 2};
      else
        arr = {halfi, 2};
    } else {
      if (is_perfect_square((unsigned long long int)(n + 1)))
        arr = {halfi + 1, n};
      else if (is_perfect_square(asdf))
        arr = {n, halfi - 2};
      else if (is_perfect_square(((long long int)halfi - 1) * (long long int)n))
        arr = {halfi - 2, n - 2};
      else
        arr = {2, halfi, n};
    }
    vector<int> ans = {};
    for (int i = 1; i < n + 1; i++) {
      if (find(arr.begin(), arr.end(), i) == arr.end()) ans.push_back(i);
    }
    cout << ans.size() << endl;
    for (int el = 0; el < ans.size(); el++) {
      cout << ans[el] << ' ';
    }
    cout << endl;
  }
  int main() {
    solve();
    return 0;
  }
  