Cho tập hợp số tự nhiên không vượt quá \(n\) (là số chẵn và cho trước)

\(S = \{1, 2, 3, 4\dots\, n-1, n\}\)

Hỏi phải lấy ít nhất bao nhiêu số từ tập hợp \(S\) để có \(2\) số sao cho tổng của chúng chia hết cho \((n + 1)\).

Rõ hơn, tìm \(x\) nhỏ nhất sao cho mọi tập con \(x\) phần tử của \(S\) tồn tại 2 số khác nhau có tổng chia hết cho \((n + 1)\).

Yêu cầu: Nhập \(n(2 \leq n \leq 10^9)\), in ra \(x\).

Example

4

3