KCOIN - Trò chơi với đồng xu

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Pirate đi shopping ở Nhật Bản và sưu tập được rất nhiều đồng xu Nhật. Khi về nhà, anh đem các đồng xu ra chơi với em gái.

Trò chơi diễn ra như sau:

  • Đầu tiên, Pirate chọn ra N đồng xu để chơi và chọn thêm một số nguyên K từ 0 đến N.
  • Trong mỗi lượt chơi, Pirate hoặc em gái của mình sẽ đưa ra một cách chọn K đồng xu sao cho cách chọn đó không trùng với bất cứ cách chọn nào đã được sử dụng trước đó.
  • Đến lượt của mình, ai không đưa ra được cách chọn nào nữa thì thua.

Pirate là một người anh mẫu mực nên anh luôn nhường em gái đi trước và luôn giành phần thua cho mình. Các bạn hãy tính xem có bao nhiêu cách chọn K để Pirate thua nhé.

Lưu ý: Một cách chọn K đồng xu là một bộ K số (a 1 , a 2 , ..., a K ) sao cho 1 ≤ a 1 < a 2 < ... < a K ≤ N. Hai cách chọn (a 1 , a 2 , ..., a K ) và (b 1 , b 2 , ..., b K ) khác nhau nếu tồn tại a i <> b i (1 ≤ i ≤ K).

Input

  • Một số nguyên N duy nhất.

Output

  • Một số nguyên duy nhất thể hiện số cách chọn K để Pirate thua.

Giới hạn

  • 1 ≤ N ≤ 10 9
  • 60% số test có 1 ≤ N ≤ 10 3
  • 80% số test có 1 ≤ N ≤ 10 5

Example 

Input:
4

Output:
2

Giải thích : Có 2 cách chọn K thỏa mãn là 0 và 4. Với K = 0, chỉ có một cách chọn các đồng xu (không chọn đồng xu nào cả) nên Pirate sẽ thua. Với K = 4 cũng tương tự.

  • Người up: voj
  • Nguồn bài: Nguyễn Xuân Khánh