Реши задачу на c++ Михаил придумал решение задачи ...

Идея: каждое соединение $i \to i+1$ можно провести только сверху или только снизу линии микроконтроллеров. При этом из-за правила “вход сверху ⇒ выход снизу (и наоборот)” стороны для проводников чередуются. Значит:

• все рёбра с нечётным $i$: $(1,2),(3,4),(5,6),\dots$ лежат на одной стороне,
• все рёбра с чётным $i$: $(2,3),(4,5),(6,7),\dots$ — на другой.

Две стороны не мешают друг другу, поэтому нужно, чтобы на каждой стороне дуги не пересекались.

Если точки (микроконтроллеры) стоят на прямой, то дуга $(u,v)$ задаёт интервал $[l,r]$, где $l=\min(pos[u],pos[v])$, $r=\max(\dots)$. Две дуги пересекаются ⇔ их интервалы частично перекрываются (есть шаблон $l_1<l_2<r_1<r_2$).

Мы добавляем рёбра по $i=1,2,\dots$. Как только при добавлении ребра $i$ на его стороне появляется пересечение — ответ равен $i$ (дальше цепочку продолжить нельзя). Если пересечений нет до конца — ответ $N$.

Чтобы быстро проверять пересечения среди уже добавленных интервалов одной стороны, поддерживаем структуру “максимальный $r$ по $l$” на позициях $1..N$ (сегментное дерево по максимуму). Для нового $[l,r]$ пересечение возможно только в двух видах:

1. Есть “контейнер” для точки $l$: интервал $[L,R]$ с $L<l<R$, но $R<r$ ⇒ пересечение. Достаточно найти правейший $L<l$ с $R>l$ (это “самый внутренний” контейнер).
2. Есть интервал, начинающийся внутри $(l,r)$, но заканчивающийся правее $r$: $\max R$ на диапазоне $(l,r)$ больше $r$.

Обе проверки делаются за $O(\log N)$. Память — ~2 сегдерева + массив позиций.

C++ решение

cpp
#include <bits/stdc++.h>
using namespace std;

struct FastScanner {
    static const int BUFSIZE = 1 << 20;
    int idx = 0, size = 0;
    char buf[BUFSIZE];

    inline char readChar() {
        if (idx >= size) {
            size = (int)fread(buf, 1, BUFSIZE, stdin);
            idx = 0;
            if (size == 0) return 0;
        }
        return buf[idx++];
    }

    int nextInt() {
        char c;
        do c = readChar(); while (c <= ' ' && c);
        int x = 0;
        while (c > ' ') {
            x = x * 10 + (c - '0');
            c = readChar();
        }
        return x;
    }
};

struct SegMax {
    int base;                 // power of two
    uint32_t *t;              // size 2*base

    SegMax(int n) {
        base = 1;
        while (base < n) base <<= 1;
        t = (uint32_t*)calloc((size_t)2 * base, sizeof(uint32_t));
    }
    ~SegMax() { free(t); }

    inline uint32_t getLeaf(int pos) const { // pos is 1-based
        return t[pos + base - 1];
    }

    inline void setPoint(int pos, uint32_t val) { // pos is 1-based
        int i = pos + base - 1;
        t[i] = val;
        for (i >>= 1; i; i >>= 1) {
            uint32_t a = t[i << 1], b = t[i << 1 | 1];
            t[i] = (a > b ? a : b);
        }
    }

    inline uint32_t rangeMax(int l, int r) const { // inclusive, 1-based
        if (l > r) return 0;
        int L = l + base - 1;
        int R = r + base - 1;
        uint32_t res = 0;
        while (L <= R) {
            if (L & 1) { res = max(res, t[L]); ++L; }
            if (!(R & 1)) { res = max(res, t[R]); --R; }
            L >>= 1; R >>= 1;
        }
        return res;
    }

    inline int descendRightmost(int node, uint32_t thr) const {
        while (node < base) {
            int right = (node << 1) | 1;
            if (t[right] > thr) node = right;
            else node = (node << 1);
        }
        return node - base + 1; // leaf position
    }

    // Find rightmost position in [l..r] whose leaf value > thr. Return 0 if none.
    inline int findRightmostGreater(int l, int r, uint32_t thr) const {
        if (l > r) return 0;
        int L = l + base - 1;
        int R = r + base - 1;

        int leftNodes[64], rightNodes[64];
        int ln = 0, rn = 0;

        while (L <= R) {
            if (L & 1) leftNodes[ln++] = L++;
            if (!(R & 1)) rightNodes[rn++] = R--;
            L >>= 1; R >>= 1;
        }

        // Check segments from right to left: rightNodes as is, then leftNodes reversed
        for (int i = 0; i < rn; i++) {
            int node = rightNodes[i];
            if (t[node] > thr) return descendRightmost(node, thr);
        }
        for (int i = ln - 1; i >= 0; i--) {
            int node = leftNodes[i];
            if (t[node] > thr) return descendRightmost(node, thr);
        }
        return 0;
    }
};

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

    FastScanner fs;
    int N = fs.nextInt();
    vector<int> pos(N + 2);

    for (int i = 1; i <= N; i++) {
        int x = fs.nextInt();
        pos[x] = i;
    }

    if (N == 1) {
        cout << 1 << "\n";
        return 0;
    }

    SegMax segOdd(N), segEven(N);

    for (int i = 1; i <= N - 1; i++) {
        int u = pos[i], v = pos[i + 1];
        int l = (u < v ? u : v);
        int r = (u < v ? v : u);

        SegMax &seg = (i & 1) ? segOdd : segEven;

        // 1) Check container crossing: exists interval starting before l, ending after l, but ending before r
        if (l > 1) {
            int contL = seg.findRightmostGreater(1, l - 1, (uint32_t)l);
            if (contL) {
                uint32_t contR = seg.getLeaf(contL);
                if ((uint32_t)r > contR) {
                    cout << i << "\n";
                    return 0;
                }
            }
        }

        // 2) Check interval starting inside (l, r) and ending after r
        if (l + 1 <= r - 1) {
            uint32_t mx = seg.rangeMax(l + 1, r - 1);
            if (mx > (uint32_t)r) {
                cout << i << "\n";
                return 0;
            }
        }

        // Insert this interval
        seg.setPoint(l, (uint32_t)r);
    }

    cout << N << "\n";
    return 0;
}

Если хочешь — могу добавить небольшой генератор тестов и/или пояснить на рисунке, почему достаточно именно этих двух проверок.