（I）在数列 $1,8,3,7,5,6,9$ 中，选取下标递增且数值递增的项。
例如选取第1、3、5、6项，对应的值为 $1, 3, 5, 6$，满足 $1<3<5<6$，故 $1,3,5,6$ 是一个长度为4的递增子列。
（II）设 $\{a_n\}$ 中长度为 $q$ 的递增子列末项的最小值为 $a_{n_0}$。
任取一个以 $a_{n_0}$ 为末项的长度为 $q$ 的递增子列，记为 $b_1, b_2, \dots, b_q$，其中 $b_q = a_{n_0}$。
由于 $p < q$，该子列的前 $p$ 项 $b_1, b_2, \dots, b_p$ 构成一个长度为 $p$ 的递增子列。
根据题意，$a_{m_0}$ 是所有长度为 $p$ 的递增子列末项中的最小值，因此该子列的第 $p$ 项 $b_p$ 必然满足 $b_p \ge a_{m_0}$。
又因为子列是严格递增的，所以 $b_q > b_p$。
综上所述，$a_{n_0} = b_q > b_p \ge a_{m_0}$，即 $a_{m_0} < a_{n_0}$。
（III）由题设，对于任意 $s \in \mathbf{N}^*$，长度为 $s$ 的递增子列末项的最小值为 $2s-1$。
这意味着：
1. 存在以 $2s-1$ 为末项的长度为 $s$ 的递增子列。
2. 不存在以小于 $2s-1$ 的数为末项的长度为 $s$ 的递增子列。
首先确定 $2k$ 与 $2k-1$ 的相对位置。
假设对于某个 $k$，数 $2k$ 出现在数 $2k-1$ 之后。
考虑 $s=k$ 的情况。若 $2k$ 在 $2k-1$ 之后，且 $2k-1$ 可以作为某个长度为 $k$ 的递增子列的末项（这是可能的，因为 $2k-1$ 是长度为 $k$ 的子列末项的最小值，说明至少有一个这样的子列），那么我们可以将 $2k$ 接在该子列之后，形成一个长度为 $k+1$、末项为 $2k$ 的递增子列。
然而，题目指出长度为 $k+1$ 的递增子列末项的最小值为 $2(k+1)-1 = 2k+1$。
如果存在末项为 $2k$ 的长度为 $k+1$ 的递增子列，则末项最小值应 $\le 2k < 2k+1$，这与题设矛盾。
因此，对于任意 $k \ge 1$，数 $2k$ 必须出现在数 $2k-1$ 之前。
接下来分析数列的具体结构。
考察前 $2s$ 个正整数 $\{1, 2, \dots, 2s\}$ 在数列 $\{a_n\}$ 中的分布。
由于 $2k$ 在 $2k-1$ 之前，对于每一对 $\{2k-1, 2k\}$，在构造递增子列时，我们不能同时选取这两个数作为相邻或不相邻但保持顺序的项来增加长度，除非它们分别来自不同的“层级”。
更严谨地，考虑长度为 $s$ 的递增子列，其末项最小值为 $2s-1$。
这意味着任何长度为 $s$ 的递增子列，其元素必然取自 $\{1, 2, \dots, 2s-1\}$ 或者包含更大的数但末项更大。
特别地，题目给出长度为 $s$ 且末项为 $2s-1$ 的递增子列恰有 $2^{s-1}$ 个。
我们用数学归纳法或构造法来确定通项。
当 $s=1$ 时，长度为1的递增子列末项最小值为 $2(1)-1=1$。末项为1的长度为1的子列有 $2^0=1$ 个。这说明 $1$ 必须出现在数列中，且在它之前没有比它小的数（显然）。同时，由前述结论，$2$ 必须在 $1$ 之前。
若 $2$ 在 $1$ 之前，数列开头可能是 $2, 1, \dots$。
检查 $s=1$：长度为1的子列末项最小值是1。子列 $\{1\}$ 存在。子列 $\{2\}$ 末项是2。最小值为1，符合。末项为1的子列只有 $\{1\}$ 这1个，符合 $2^{1-1}=1$。
当 $s=2$ 时，长度为2的递增子列末项最小值为 $2(2)-1=3$。末项为3的长度为2的子列有 $2^{2-1}=2$ 个。
已知 $2$ 在 $1$ 之前，$4$ 在 $3$ 之前。
为了形成末项为3的长度为2的递增子列，我们需要在 $3$ 之前找到一个比 $3$ 小的数 $x$，使得 $x, 3$ 构成递增子列。
可能的 $x$ 为 $1$ 或 $2$。
如果数列片段顺序为 $2, 1, 4, 3$，则：
- 以3结尾的长度为2的递增子列有：$(1, 3)$ 和 $(2, 3)$。注意这里 $2$ 在 $1$ 前，$1$ 在 $3$ 前，$2$ 也在 $3$ 前。
- 子列 $(1,3)$：$1$ 的索引小于 $3$ 的索引，$1<3$，合法。
- 子列 $(2,3)$：$2$ 的索引小于 $3$ 的索引，$2<3$，合法。
- 是否有其他？$(4,3)$ 不递增。$(2,1)$ 不递增。
- 所以恰有2个，符合 $2^{2-1}=2$。
- 此时长度为2的末项最小值：$(2,3)$ 末项3，$(1,3)$ 末项3，$(2,4)$ 末项4，$(1,4)$ 末项4... 最小值为3，符合 $2s-1=3$。
推测数列规律为每两个数一组，偶数在前，奇数在后，即 $2, 1, 4, 3, 6, 5, \dots$。
通项公式为：
当 $n$ 为奇数时，$a_n = n+1$；
当 $n$ 为偶数时，$a_n = n-1$。
即 $a_{2k-1} = 2k, a_{2k} = 2k-1$。
验证一般情况 $s$：
在此数列中，前 $2s$ 项包含集合 $\{1, 2, \dots, 2s\}$。
其中 $2k$ 排在 $2k-1$ 前面 ($k=1,\dots,s$)。
且组与组之间，$2k$ (第 $2k-1$ 项) 和 $2k-1$ (第 $2k$ 项) 整体排在 $2(k+1)$ 和 $2(k+1)-1$ 之前。
具体来说，$a_1=2, a_2=1, a_3=4, a_4=3, \dots, a_{2s-1}=2s, a_{2s}=2s-1$。
我们要找长度为 $s$ 且末项为 $2s-1$ 的递增子列。
末项固定为 $a_{2s} = 2s-1$。
我们需要从前 $2s-1$ 项中选出 $s-1$ 项 $b_1 < b_2 < \dots < b_{s-1} < 2s-1$，且下标递增。
可用的数值为 $\{1, 2, \dots, 2s-2\}$。
这些数值分为 $s-1$ 组：$\{2,1\}, \{4,3\}, \dots, \{2s-2, 2s-3\}$。
在第 $j$ 组 $\{2j, 2j-1\}$ 中，$2j$ 的下标是 $2j-1$，$2j-1$ 的下标是 $2j$。
为了构成递增序列，如果我们从第 $j$ 组选数，只能选一个（因为同一组内大数在前小数在后，不能同时选构成递增）。
而且，为了保持整个子列递增，若我们从第 $j$ 组选了数 $x_j$，从第 $k$ 组选了数 $x_k$ ($j<k$)，必须满足 $x_j < x_k$ 且 $index(x_j) < index(x_k)$。
由于组是按顺序排列的，只要我们在每组中选出的数满足数值递增即可。
在第 $j$ 组 $\{2j, 2j-1\}$ 中，无论选 $2j$ 还是 $2j-1$，其值都大于第 $j-1$ 组的所有数（最大 $2j-2$ 或 $2j-3$），且小于第 $j+1$ 组的所有数。
实际上，第 $j$ 组的两个数 $2j, 2j-1$ 都介于 $2j-2$ 和 $2j+1$ 之间。
更精确地说，若我们从每组 $\{2k, 2k-1\}$ ($k=1, \dots, s-1$) 中各选一个数，共有 $2^{s-1}$ 种选法。
设选出的数为 $c_1, c_2, \dots, c_{s-1}$，其中 $c_k \in \{2k, 2k-1\}$。
显然 $c_1 < c_2 < \dots < c_{s-1}$ 恒成立吗？
$c_k$ 的最小值是 $2k-1$，最大值是 $2k$。
$c_{k+1}$ 的最小值是 $2(k+1)-1 = 2k+1$。
因为 $2k < 2k+1$，所以无论怎么选，都有 $c_k < c_{k+1}$。
同时，下标方面：若选 $2k$，下标为 $2k-1$；若选 $2k-1$，下标为 $2k$。
若选 $2(k+1)$，下标为 $2k+1$；若选 $2(k+1)-1$，下标为 $2k+2$。
无论 $c_k$ 选哪个，其下标 $idx_k \le 2k$。
无论 $c_{k+1}$ 选哪个，其下标 $idx_{k+1} \ge 2k+1$。
所以 $idx_k < idx_{k+1}$ 恒成立。
因此，从前 $s-1$ 组中每组任选一个数，都能与最后的 $2s-1$ 构成一个长度为 $s$ 的递增子列。
这样的子列个数正是 $2^{s-1}$。
且末项均为 $2s-1$。
是否存在末项更小（即 $<2s-1$）的长度为 $s$ 的递增子列？
长度为 $s$ 的递增子列至少需要 $s$ 个不同的正整数。最小的 $s$ 个正整数是 $1, \dots, s$。
但在我们的数列结构中，要凑齐 $s$ 个递增的数，必须跨越至少 $s$ 个“值域层级”。
事实上，由（II）的结论推广，长度为 $s$ 的递增子列末项最小值即为 $2s-1$。
此构造满足所有条件。
故数列通项公式为：
$a_n = \begin{cases} n+1, & n \text{ 为奇数} \\ n-1, & n \text{ 为偶数} \end{cases}$