<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

178. Golden chain
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard
output: standard



Peter arrived to the city and stayed in the hotel. He has no money but few day's later (maximum N days) he will receive a lot of money. And so he has a golden chain with N links. Peter must pay one link everyday, but he can pay more and take change by some of his links paid before.
When he receives money he will get his chain out of pawn. Peter likes his chain and he wants to break minimal number of links. Help him!
For example, if N=5, he must break one link (the second). After it his chain will consist of 3 parts with lengths 1, 1 and 3.
At the first day he will pay one link, at the second - one link too. Now he have one part consists of three connected links. At the third day he will pay 3-linked part and take two separated links (as change) back. On the fourth and fifth day he will pay one link.
You may assume that Peter can choose the way to get change.

Input
Input contains one integer number N (1<=N<=10^16).

Output
In output file you must write one integer number (number of the broken links).

Sample test(s)

Input
9

Output
2
Author:	Vasiliy Astakhov
Resource:	Saratov ST team Spring Contest #1
Date:	18.05.2003

<|response|>
1. Abridged problem statement  
Given a chain of N links, you need to pay exactly one link per day for N days by pawning whole connected segments (and receiving previously pawned single links as change). Initially you may break some links to create loose rings (connectors). What is the minimum number of links to break so that you can pay one link each day for N consecutive days?

2. Key observations  
- If you break k links up front, you obtain k loose rings and the remaining chain splits into k+1 connected segments.  
- On each day you hand over one or more entire segments or loose rings to the pawnbroker and receive back some loose rings from previous days so that your net payment is exactly one link.  
- With an optimal choice of where to break, the maximum number of days you can cover using k breaks is  
  M(k) = (k+1) × 2^(k+1) − 1.  
- We need the smallest k such that M(k) ≥ N.

3. Full solution approach  
a. Derive M(k):  
   - Base case k=0 (no breaks): you have one segment of length N, no loose rings; you can only pay on day 1. M(0)=1=(0+1)·2^(0+1)−1.  
   - When you go from k−1 breaks to k breaks, you double your reachable days and add one more full block, yielding the recurrence M(k) = 2·M(k−1) + 1, which solves to M(k) = (k+1)·2^(k+1) − 1.  
b. To find the minimum k with M(k) ≥ N, observe that M(k) grows very quickly (exponentially in k). We can simply loop k = 0,1,2,… and compute M(k) until it reaches or exceeds N.  
c. Instead of recomputing powers every time, maintain two variables:  
   - ans = current k, initialized to 0  
   - x = 2^(ans+1), initialized to 2  
   Then M(ans) = x·(ans+1) − 1.  
   In each iteration, if x·(ans+1) − 1 < N, increment ans and double x.  
d. When the loop finishes, ans is the minimum number of breaks required.  

4. C++ implementation  
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t n;

void read() { cin >> n; }

void solve() {
    // With b broken links we get b single loose links plus b + 1 intact
    // segments. The b loose links can make change for any value 1..b directly,
    // and the segments (chosen with the classic 1, 2, 4, ..., 2^b sizes) let us
    // cover everything up to (b + 1) * 2^b - 1 days, where the -1 accounts for
    // the loose links being part of the total. So we find the smallest b with
    // (b + 1) * 2^b - 1 >= n by incrementing b while the bound is still below.

    int64_t x = 2, ans = 0;
    while(x * (ans + 1) - 1 < n) {
        ans++;
        x *= 2;
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys

def main():
    data = sys.stdin.read().strip()
    if not data:
        return
    n = int(data)

    # ans = number of links to break
    # x = 2^(ans+1); start with ans=0 => x=2
    ans = 0
    x = 2

    # M(ans) = x * (ans+1) - 1
    # Loop until M(ans) >= n
    while x * (ans + 1) - 1 < n:
        ans += 1
        x <<= 1  # same as x *= 2

    print(ans)

if __name__ == "__main__":
    main()
```
