已知数列 $\{a_n\}$，从中选取第 $i_1$ 项，第 $i_2$ 项，…，第 $i_m$ 项（$i_1<i_2<\cdots<i_m$），若 $a_{i_1}<a_{i_2}<\cdots<a_{i_m}$，则称新数列 $a_{i_1}$，$a_{i_2}$，$\dots$，$a_{i_m}$ 为 $\{a_n\}$ 的长度为 $m$ 的递增子列. 规定：数列 $\{a_n\}$ 的任意一项都是 $\{a_n\}$ 的长度为 $1$ 的递增子列.

(1) 写出数列 $1$，$8$，$3$，$7$，$5$，$6$，$9$ 的一个长度为 $4$ 的递增子列； (2) 已知数列 $\{a_n\}$ 的长度为 $p$ 的递增子列的末项的最小值为 $a_{m_0}$，长度为 $q$ 的递增子列的末项的最小值为 $a_{n_0}$. 若 $p<q$，求证：$a_{m_0}<a_{n_0}$； (3) 设无穷数列 $\{a_n\}$ 的各项均为正整数，且任意两项均不相等. 若 $\{a_n\}$ 的长度为 $s$ 的递增子列末项的最小值为 $2s-1$，且长度为 $s$ 末项为 $2s-1$ 的递增子列恰有 $2^{\,s-1}$ 个（$s=1$，$2$，$\dots$），求数列 $\{a_n\}$ 的通项公式.