Любимая последовательность чисел 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$$$.