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;
  constexpr long long MOD = 998244353;
  int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    long long n;
    cin >> n;
    auto is_sq = [&](long long x) {
      return (long long)sqrt(x) * (long long)sqrt(x) == x;
    };
    auto get_wont = [&]() -> vector<long long> {
      if (n % 4 == 0)
        return {n / 2};
      else if (n == 1)
        return {};
      else if (n % 4 == 1) {
        return {n / 2, n};
      } else if (n % 4 == 2) {
        if (is_sq(n + 2))
          return {n / 2 + 1};
        else if (is_sq(n * (n / 2 + 1)))
          return {n / 2 - 2};
        else
          return {n / 2, 2};
      } else {
        if (is_sq(n + 1))
          return {n / 2 + 1, n};
        else if (is_sq(2 * (n / 2) * (n / 2 - 1)))
          return {n / 2 - 2, n};
        else if (is_sq((n / 2 - 1) * n))
          return {n / 2 - 2, n - 2};
        else
          return {2, n / 2, n};
      }
    };
    auto wont = get_wont();
    cout << n - wont.size() << "\n";
    for (int i = 1; i <= n; i++)
      if (find(wont.begin(), wont.end(), i) == wont.end()) cout << i << " ";
    cout << "\n";
  }
  