　$\varphi = \dfrac{1 + \sqrt5}{2}$ とし，$a_n = \lfloor\varphi n\rfloor + 1$ であることを示す．\
　$n = 1$ のとき，明らかに成立する．また，$n = 1,2,\ldots,k$ で成立しているとき，
$$\begin{aligned}
a_{k+1} &= k+2 + \\#\big(\\{1,2,\ldots,k+1\\}\cap\\{a_1,a_2,\ldots,a_k\\}\big)\\\\
&= k+2 + \\#\big(\\{0,1,\ldots,k\\}\cap\\{\lfloor\varphi\rfloor,\lfloor2\varphi\rfloor,\ldots,\lfloor k\varphi\rfloor\\}\big)
\end{aligned}$$
である．ここで，$\\#\big(\\{0,1,\ldots,k\\}\cap\\{\lfloor\varphi\rfloor,\lfloor2\varphi\rfloor,\ldots,\lfloor k\varphi\rfloor\\}\big)$ は，$\lfloor t\varphi\rfloor \lt k+1$ なる正の整数 $t$ の個数であるので，$\varphi$ が無理数であることと併せて $\bigg\lfloor \dfrac {k+1}\varphi\bigg\rfloor$ である．従って，$\varphi = 1 + \dfrac 1\varphi$ より，
$$a_{k+1} = k+2 + \bigg\lfloor \dfrac {k+1}\varphi\bigg\rfloor = k+2 + \lfloor (k+1)\varphi - (k+1)\rfloor = \lfloor (k+1)\varphi\rfloor + 1$$
である．以上より，帰納法によって示された．\
　特に，求める答えは，
$$a_{10^{5}} = \lfloor 10^{5}\varphi\rfloor + 1 = \bf{161804}$$
である．
公式解説
https://onlinemathcontest.com/contests/omc190/editorial/6631
　ここではどこから $\dfrac{1 + \sqrt{5}}{2}$ がでてきたか(自分の場合の話ですが)書いていきたいと思います．\
まず，$a_{n}$ を小さな値から順に求めていくと，Fibonacci数列( $b_{n + 2} = b_{n + 1} + b_{n} , b_{1} = b_{2} = 1$ ) が $a_{b_{n}} = b_{n + 1}$ または $a_{b_{n}} = b_{n + 1} + 1$ という形で出てきていることがわかります(実際に帰納法で示すことができます)．ここで思い出すのが数列 ${b_{n}}$ の比率の話で

$$\lim_{n \to \infty} {\dfrac{b_{n + 1}}{b_{n}}} = \dfrac{1 + \sqrt{5}}{2}$$

になることが知られてます．そこから漸化式の形も考慮すると公式解説のような予測が立ちます．
公式解説のような予想を立てるまで
https://onlinemathcontest.com/contests/omc190/editorial/6631/339
　$a_n=\lfloor\frac{1+\sqrt{5}}{2}n\rfloor+1$ の別証です．  
  
　明らかに $a_{n+1}\gt a_n\geq n+1$ なので，題意より  
$$a_n=a_1+1×(n-1-\\#(k|a_k\leq n))+2×\\#(k|a_k\leq n)=n+1+\\#(k|a_k\leq n)$$
がわかる．  
　以降，数学的帰納法で $a_n=\lfloor\frac{1+\sqrt{5}}{2}n\rfloor+1$ を示す．  
　$n=1$ のときは明らかに成り立つ．  
　$n\leq m$ のとき成り立つとする．このとき，$m+1\geq 2，a_{n+1}-a_n\leq 2$ より $a_l=m+1$ または $a_l=m+2$ なる整数 $l$ をとれる．  
　$a_l=m+1$ なる $l$ が存在するとき，
$$a_{m+1}=a_{a_l}= a_l+1+\\#(k|a_k\leq a_l)=l+m+2$$
である．$\frac{1+\sqrt{5}}{2}l$ が整数となることは明らかにないので，$a_l=m+1$ より $$\frac{1+\sqrt{5}}{2}l-1\lt m\lt \frac{1+\sqrt{5}}{2}l$$
であることから
$$\frac{1+\sqrt{5}}{2}(m+1)=\frac{-1+\sqrt{5}}{2}m+m+\frac{1+\sqrt{5}}{2}\gt \frac{-1+\sqrt{5}}{2}(\frac{1+\sqrt{5}}{2}l-1)+m+\frac{1+\sqrt{5}}{2}=l+m+1$$
$$\frac{1+\sqrt{5}}{2}(m+1)=\frac{-1+\sqrt{5}}{2}m+m+\frac{1+\sqrt{5}}{2}\lt l+m+2$$
となるため
$$\lfloor \frac{1+\sqrt{5}}{2}(m+1)\rfloor+1=l+m+2=a_{m+1}$$
がわかる．  
　そうでないときは，$a_l=m+2$ なる $l$ が存在するので
$$a_{m+1}=a_{a_l-1}= (a_l-1)+1+\\#(k|a_k\leq a_l-1)=l+m+1$$
である．$a_l=m+2$ より
$$\frac{1+\sqrt{5}}{2}l-2\lt m\lt \frac{1+\sqrt{5}}{2}l-1$$
となり，先程と同様の議論から
$$l+m\lt \frac{1+\sqrt{5}}{2}(m+1)\lt l+m+1$$
がわかるので
$$\lfloor \frac{1+\sqrt{5}}{2}(m+1)\rfloor+1=l+m+1=a_{m+1}$$
である．  
　以上より，$n=m+1$ のときも成立することが示せた．  
　したがって，$a_n=\lfloor\frac{1+\sqrt{5}}{2}n\rfloor+1$ がわかる．  
  
　余談ですが，
$$a_{a_n}=a_n+1+\\#(k|a_k\leq a_n)=a_n+n+1$$
より，$b_1=n，b_{n+1}=a_{b_n}$ とおいて $b_n$ についての三項間漸化式の特性方程式を解くことで $\frac{1+\sqrt{5}}{2}$ という値が何とは無しに見えたりします．
ユーザー解説
https://onlinemathcontest.com/contests/omc190/editorial/6631/356
　数列 $\\{a_n\\}\_{n=1,2,\ldots}$ が以下を満たすとき，$a_{10^{5}}$ の値を求めてください．
- $a_1 = 2.$
- 任意の $2$ 以上の整数 $n$ について，$n\in \\{a_1,a_2,\ldots,a_{n-1}\\}$ ならば $a_n = a_{n-1} + 2$ であり，そうでないならば $a_n = a_{n-1} + 1$ である．