Любимая последовательность чисел Touko — это перестановка \(a_1, a_2, \dots, a_n\) чисел \(1, 2, \dots, n\), и она хочет коллекцию перестановок, похожих на ее любимую перестановку.
У нее есть коллекция \(q\) отрезков вида \([l_i, r_i]\) с \(1 \le l_i \le r_i \le n\). Для создания перестановок, похожих на ее любимую перестановку, она придумала следующее определение:
- Перестановка \(b_1, b_2, \dots, b_n\) позволяет интервалу \([l', r']\) удерживать свою форму, если для любой пары целых \((x, y)\) таких, что \(l' \le x < y \le r'\), неравенство \(b_x < b_y\) выполняется тогда и только тогда, когда \(a_x < a_y\).
- Перестановка \(b_1, b_2, \dots, b_n\) называется \(k\)-похожей, если \(b\) позволяет всем интервалам \([l_i, r_i]\) для \(1 \le i \le k\) сохранять свою форму.
Yuu хочет найти все \(k\)-похожие перестановки для Touko, но это оказалось очень сложной задачей. Вместо этого Yuu будет кодировать набор всех \(k\)-похожих перестановок ориентированными ациклическими графами (DAG). Yuu также придумала для себя следующие определения:
- Перестановка \(b_1, b_2, \dots, b_n\) удовлетворяет DAG \(G'\), если для всех ребер \(u \to v\) в \(G'\) выполняется \(b_u < b_v\).
- \(k\)-кодирование — это DAG \(G_k\) на наборе вершин \(1, 2, \dots, n\) такой, что перестановка \(b_1, b_2, \dots, b_n\) удовлетворяет \(G_k\), если и только если \(b\) является \(k\)-похожей.
Поскольку Yuu сегодня свободна, она хочет выяснить минимальное количество ребер среди всех \(k\)-кодирований для каждого \(k\) от \(1\) до \(q\).