Hai tập hợp

Nguồn: CSES Problem Set

Đề bài

Hãy chia các số nguyên $1,2,\ldots,n$ thành hai tập hợp sao cho tổng các phần tử của hai tập hợp bằng nhau.

Nếu tồn tại cách chia như vậy, hãy đưa ra một cách chia hợp lệ.

Input

Dòng duy nhất chứa một số nguyên $n$.

Output

Nếu không thể chia các số $1,2,\ldots,n$ thành hai tập hợp có tổng bằng nhau, in ra NO.

Ngược lại, in ra YES, sau đó mô tả hai tập hợp:

• Trên một dòng, in số lượng phần tử của tập hợp thứ nhất.
• Trên dòng tiếp theo, in các phần tử của tập hợp thứ nhất, cách nhau bởi dấu cách.
• Trên một dòng, in số lượng phần tử của tập hợp thứ hai.
• Trên dòng tiếp theo, in các phần tử của tập hợp thứ hai, cách nhau bởi dấu cách.

Có thể in ra bất kỳ cách chia nào thỏa mãn yêu cầu.

Subtask

• Subtask 1 — 15%: $1 \le n \le 20$.
• Subtask 2 — 30%: $1 \le n \le 400$.
• Subtask 3 — 55%: $1 \le n \le 10^6$.

Ví dụ

Ví dụ 1

Input

7

Output

YES
4
1 2 4 7
3
3 5 6

Giải thích

Với $n=7$, tổng các số từ $1$ đến $7$ bằng

Tập hợp thứ nhất gồm $1,2,4,7$, có tổng

Tập hợp thứ hai gồm $3,5,6$, có tổng

Hai tập hợp không có phần tử chung, chứa đầy đủ các số từ $1$ đến $7$ và có tổng bằng nhau, vì vậy cách chia trong Output là hợp lệ.

Ví dụ 2

Input

6

Output

NO

Giải thích

Với $n=6$, tổng các số từ $1$ đến $6$ bằng

Vì $21$ là số lẻ nên không thể chia toàn bộ các số này thành hai tập hợp có tổng bằng nhau. Do đó Output là NO.