已知数列{a_n}，从中选取第i₁项、第i₂项…第i_m项（i₁<i₂<…<i_m）.若a_i1<a_i2<…<a_im.则称新数列a_i1 ， a_i2 ， …，a_im.为{a_n}的长度为m的递增子列.规定：数列{a_n}的任意一项都是{a_n}的长度为1的递增子列.

（I）写出数列1，8，3，7，5，6，9的一个长度为4的递增子列；

（II）已知数列{a_n}的长度为P的递增子列的末项的最小值为a_m0 ， 长度为q的递增子列的末项的最小值为a_n0 ， 若p<q，求证：a_m0<a_n0；

（III）设无穷数列{a_n}的各项均为正整数，且任意两项均不相等。若{a_n}的长度为s的递增子列末项的最小值为2s-1，且长度为s末项为2s-1的递增子列恰有2^s-1个（s=1.2.…），求数列{a_n}的通项公式。