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

Идея

Пусть микроконтроллеры стоят слева направо в порядке перестановки p[1..N]. Обозначим pos[x] — позицию микроконтроллера с номером x на плате.

Нужно провести дорожки для цепочки 1–2–…–m так, чтобы:

• все дорожки лежали в одной плоскости и не пересекались;
• дорожки можно вести только сверху или снизу от линии (между микроконтроллерами и вокруг концов нельзя);
• в каждом микроконтроллере вход и выход обязательно с разных сторон, значит соседние ребра пути должны идти по разным сторонам.

Следствие: если выбрать, где идет первое соединение 1–2 (сверху или снизу), то дальше стороны строго чередуются. То есть есть всего 2 варианта.

Остается для каждого варианта проверить, как далеко можно дойти, добавляя ребра (i, i+1) по одному, пока не появится пересечение на той стороне, куда это ребро попадает.

---

Как проверять пересечение на одной стороне

Рассмотрим одну сторону (например, верх). Там ребра не имеют общих вершин (из-за чередования), значит это matching: набор непересекающихся по вершинам дуг между точками на прямой.

Для каждого уже добавленного ребра между позициями L<R мы храним:

• mate[L]=R, mate[R]=L (для остальных позиций “пусто”).

Новое ребро [L,R] пересечется с уже существующими тогда и только тогда, когда внутри (L,R) найдется конец какого-то ребра, чей парный конец лежит вне (L,R):

• либо mate[x] < L (торчит налево),
• либо mate[x] > R (торчит направо).

Значит достаточно уметь быстро находить на отрезке (L,R):

• min(mate[x])
• max(mate[x])

Если min < L или max > R — пересечение неизбежно.

Это делается итеративным сегментным деревом (range min/max + point update).

---

Сложность

• Память: O(N) (позиции + 2 сегдерева (верх/низ) с min/max).
• Время: O(N log N) (каждое ребро: 1 запрос + 2 обновления в одном из деревьев).

---

Решение на C++

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

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

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

    template <class T>
    bool readInt(T &out) {
        char c;
        do {
            c = readChar();
            if (!c) return false;
        } while (c <= ' ');

        bool neg = false;
        if (c == '-') { neg = true; c = readChar(); }

        T val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = readChar();
        }
        out = neg ? -val : val;
        return true;
    }
};

static inline void segUpdate(int *mn, int *mx, int base, int pos, int val) {
    int i = pos + base;
    mn[i] = val;
    mx[i] = val;
    i >>= 1;
    while (i) {
        int l = i << 1;
        int r = l | 1;
        mn[i] = (mn[l] < mn[r]) ? mn[l] : mn[r];
        mx[i] = (mx[l] > mx[r]) ? mx[l] : mx[r];
        i >>= 1;
    }
}

static inline void segQuery(int *mnArr, int *mxArr, int base, int l, int r, int &mnRes, int &mxRes) {
    // query on [l, r), 0-indexed
    const int INF = 0x3f3f3f3f;
    mnRes = INF;
    mxRes = 0;
    l += base;
    r += base;
    while (l < r) {
        if (l & 1) {
            mnRes = (mnArr[l] < mnRes) ? mnArr[l] : mnRes;
            mxRes = (mxArr[l] > mxRes) ? mxArr[l] : mxRes;
            ++l;
        }
        if (r & 1) {
            --r;
            mnRes = (mnArr[r] < mnRes) ? mnArr[r] : mnRes;
            mxRes = (mxArr[r] > mxRes) ? mxArr[r] : mxRes;
        }
        l >>= 1;
        r >>= 1;
    }
}

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

    FastScanner fs;
    int N;
    if (!fs.readInt(N)) return 0;

    vector<int> pos(N + 1);
    for (int i = 0; i < N; i++) {
        int x; fs.readInt(x);
        pos[x] = i; // 0-index position on the board
    }

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

    const int INF = 0x3f3f3f3f;
    const int base = N;
    const size_t SZ = 2ull * base;
    const size_t BYTES = SZ * sizeof(int);

    // Two segment trees: top and bottom, each needs min and max arrays
    int *topMin = (int*)malloc(BYTES);
    int *topMax = (int*)malloc(BYTES);
    int *botMin = (int*)malloc(BYTES);
    int *botMax = (int*)malloc(BYTES);

    auto compute = [&](bool firstEdgeTop) -> int {
        // init: min = INF, max = 0
        memset(topMin, 0x3f, BYTES);
        memset(botMin, 0x3f, BYTES);
        memset(topMax, 0x00, BYTES);
        memset(botMax, 0x00, BYTES);

        for (int i = 1; i <= N - 1; i++) {
            // edge (i, i+1)
            bool isTop = (i & 1) ? firstEdgeTop : !firstEdgeTop;

            int a = pos[i];
            int b = pos[i + 1];
            int L = (a < b) ? a : b;
            int R = (a < b) ? b : a;

            int *mnArr = isTop ? topMin : botMin;
            int *mxArr = isTop ? topMax : botMax;

            if (L + 1 < R) {
                int mnInside, mxInside;
                segQuery(mnArr, mxArr, base, L + 1, R, mnInside, mxInside);
                if (mnInside < L || mxInside > R) {
                    return i; // cannot add (i, i+1) => max m = i
                }
            }

            // add endpoints: mate[a]=b, mate[b]=a
            segUpdate(mnArr, mxArr, base, a, b);
            segUpdate(mnArr, mxArr, base, b, a);
        }
        return N;
    };

    int ans = max(compute(true), compute(false));
    cout << ans << "\n";

    free(topMin);
    free(topMax);
    free(botMin);
    free(botMax);
    return 0;
}

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