Tade vừa nhận việc tại Khách sạn Hilbert, đảm nhận việc vận chuyển hành lý giữa vô hạn các căn phòng và vô hạn các tầng của khách sạn. Một ngày nọ, khi đang đi giao hành lý, Tade bước vào thang máy để di chuyển giữa các tầng. Không may, ngay khi cửa đóng lại, hệ thống điều khiển gặp sự cố. Thay vì nhận lệnh từ người dùng, chiếc thang máy bắt đầu tự di chuyển theo một quy luật kỳ lạ:

Ban đầu, thang máy đứng ở tầng \(0\). Ở bước thứ \(i\) \((i \ge 1)\), thang máy sẽ cố gắng đi xuống \(i\) tầng, nếu tầng đó âm hoặc thang máy đã từng ghé qua tầng đó trước đây thì thang máy sẽ đổi ý và đi lên \(i\) tầng (dữ liệu đảm bảo thang máy sẽ không bao giờ đi lên tầng đã đi qua).

Lo lắng không biết mình sẽ bị đưa tới đâu, Tade muốn biết sau đúng \(n\) bước di chuyển, thang máy sẽ dừng ở tầng nào.

Input

• Một số nguyên không âm \(n\) \((1 \le n \le 3 \times 10^5)\).
• Dữ liệu đảm bảo thang máy không đi quá tầng thứ \(2 \times 10^6\).

Output

• In ra số tầng mà thang máy đứng tại sau \(n\) bước.

Example

6

13