Loại bỏ lá bài II (Throwing Cards Away II)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có một bộ bài gồm $n$ lá, được đánh số từ $1$ đến $n$. Lá $1$ ở trên cùng, lá $n$ ở dưới cùng.

Khi còn ít nhất hai lá, lặp lại hai thao tác theo đúng thứ tự:

1. bỏ lá trên cùng;
2. chuyển lá đang ở trên cùng xuống dưới cùng.

Hãy tìm số trên lá bài cuối cùng còn lại.

Input

Một số nguyên dương $n$.

Output

In số của lá bài cuối cùng còn lại.

Subtask

• Subtask 1 (20%): $n\le100$.
• Subtask 2 (30%): $101\le n\le10000$.
• Subtask 3 (50%): Đầy đủ: $1\le n\le500000$.

Ví dụ

Input

7

Output

6

Giải thích

Bắt đầu với 1 2 3 4 5 6 7. Bộ bài thay đổi theo từng lượt như sau:

• Bỏ 1, rồi chuyển 2 xuống cuối: 3 4 5 6 7 2.
• Bỏ 3, rồi chuyển 4 xuống cuối: 5 6 7 2 4.
• Bỏ 5, rồi chuyển 6 xuống cuối: 7 2 4 6.
• Bỏ 7, rồi chuyển 2 xuống cuối: 4 6 2.
• Bỏ 4, rồi chuyển 6 xuống cuối: 2 6.
• Bỏ 2, chỉ còn lại lá 6.

Vì vậy chương trình in 6.