BannerWithNails

This problem and the division 2 easy problem NailingABanner are two different problems. Make sure to read the statement carefully to note the differences.

You were asked to attach a very long banner to an equally long wooden fence. You did that by using some nails.

The banner is exactly 2^60 (two to the power of 60) units long.

You started by using the first nail to attach the top left corner of the banner to the fence and then the second nail to attach the top right corner. The location of the first nail is coordinate 0, the location of the second nail is coordinate 2^60.

From this point on, you were adding more nails to the banner. The nails were added in rounds. In each round, you first identified all pairs of nails that were currently adjacent (i.e., had no other nail between them), and then for each such pair you placed another nail exactly half-way between the two adjacent nails. Within each round, these new nails were placed from the left to the right, i.e., their coordinates increased.

For example:

• Round 1: Exactly one nail (nail #3) was placed into the middle of the banner.
• Round 2: We placed two nails. Nail #4 was placed between nails #1 and #3, and then nail #5 was placed between nails #3 and #2. (Nail #4 is in one fourth of the banner, nail #5 is in its three fourths.)
• Round 3: The five nails we had already placed formed four pairs of adjacent nails. Thus, in this round we added four new nails - one into the middle of each of the four segments of the banner.

The process terminated after placing the nail number 2^60 + 1. It can be shown that at this moment there were nails precisely at all integer coordinates between 0 and 2^60, inclusive.

You are given the coordinate X of a nail. Return the number of this nail.