#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <climits>

using namespace std;

struct puperfunctionmycreateion{
    int data, prev, st, ans;
};

int main()
{
    puperfunctionmycreateion temp, temp1;
    int n, m, free = 0, v, u, h;
    vector <int> a,head, ans, next, dest;
    queue <puperfunctionmycreateion> q;
    //cin >> n >> m;
    n = 1000000;
    m = n - 1;
    head.reserve(1000000);
    a.reserve(1000000);
    ans.reserve(1000000);
    dest.reserve(1000000);
    next.reserve(1000000);
    head.resize(n + 1);
    ans.resize(n + 1);
    a.resize(n + 1);
    for (int i = 1; i <= n; i++){
        next[i] = 0;
        ans[i] = INT_MAX - 20;
        //cin >> a[i];
        if (i == 1 || i == n)
            a[i] = i;
        else
            a[i] = 0;
        if (a[i] != 0){
            temp.data = i;
            temp.st = i;
            temp.ans = 0;
            temp.prev = 0;
            q.push(temp);
        }
    }
    for (int i = 1; i <= m; i++){
        //cin >> v >> u;
        v = i;
        u = i + 1;
        free++;
        dest.resize(free + 1);
        next.resize(free + 1);
        dest[free] = u;
        next[free] = head[v];
        head[v] = free;
        free++;
        dest.resize(free + 1);
        next.resize(free + 1);
        dest[free] = v;
        next[free] = head[u];
        head[u] = free;
    }
    while (!q.empty()){
        temp = q.front();
        h = head[temp.data];
        while (h){
        if (dest[h] != temp.prev)
            if (a[dest[h]] == 0){
                temp1.data = dest[h];
                temp1.st = temp.st;
                temp1.ans = temp.ans + 1;
                temp1.prev = temp.data;
                q.push(temp1);
            }
            else
                if (a[dest[h]] != a[temp.st])
                    ans[dest[h]] = min(ans[dest[h]], temp.ans + 1);
            h = next[h];
        }
        q.pop();
    }
    int min2;
    min2 = ans[1];
    for (int i = 2; i <= n; i++)
        min2 = min(min2, ans[i]);
    cout << min2 << endl;
    return 0;
}