First, let $p=q$, so $p\mid a^p+1$. By Fermat, $a^p+1\equiv a+1\pmod{p}$, so $p\mid a+1$. Hence assume $p<q$ without loss. Let $d$ be the smallest positive integer such that $p\mid a^d-1$. Using $a^q\equiv -1\pmod{p}$, $a^{2q}\equiv 1\pmod{p}$ and $p>2$, we get that $d\nmid q$ and $d\mid 2q$. So, $d\in\{2,2q\}$. Furthermore, $a^{p-1}\equiv 1\pmod{p}$ by Fermat, so $d\mid p-1$, as well. Now since $p<q$, $d=2q$ is impossible by size reasons, so $d=2$. With this, $p\mid (a-1)(a+1)$. If $a\equiv 1\pmod{p}$, then $a^p+1\equiv 2\pmod{p}$, not possible since $p\ne 2$. So, $p\mid a+1$, as desired.

First of all let $p=q$, this yields $a^p+1\overset{\text{FLT}}{\equiv}a+1\pmod p$ however since $p\mid a^p+1$ we have that $p\mid a+1$ So from now on $\text{ WLOG }$ assume that $p<q$ Rewriting the first condition yields $a^q+1\equiv 0\pmod p\Longrightarrow a^q\equiv-1\pmod p\text{ thus }a^{2q}\equiv1\pmod p$ Now let $\operatorname{ord}_p(a)=c$ for some $c\in\mathbb{Z}$, now using the fact that $a^{2q}\equiv1\pmod p$ we have that $c\mid 2q$ thus $c\in\{1,2,q,2q\}$ $c=1$ yields $a\equiv 1\pmod p$ thus $a^q+1\equiv 2\pmod p\Longrightarrow 2\equiv 0\pmod p$ which is clearly a contradiction. $c=q$ yields $a^q\equiv 1\pmod p$ thus $a^q+1\equiv 2\pmod p\Longrightarrow 2\equiv0\pmod p$ which is also clearly a contradiction. $c=2q$ yields $a^2q\equiv 1\pmod p\Longrightarrow\operatorname{ord}_p(a)=2q\mid p-1$ thus $2q\le p-1$ However notice that from our assumption we have that $p-1<p<q<2q$ which forces $2q\le p-1<2q$ which is a contradiction. Therefore $c=2$ which implies $a^2\equiv 1\pmod p\Longleftrightarrow (a+1)(a-1)\equiv0\pmod p$, if $a-1\equiv 0\pmod p\Longrightarrow a\equiv 1\pmod p$ However this forces $a^q+1\equiv 2\pmod p\Longrightarrow2\equiv0\pmod p$ which is a contradiction. Thus $a+1\equiv 0\pmod p\Longleftrightarrow p\mid a+1$ $\blacksquare$.

Let $p \leq q$, we have $a^q \equiv -1 \pmod{p} \implies a^{2q} \equiv 1 \pmod{p} \implies \operatorname{ord}_p(a) \mid 2q$. Let $\operatorname{ord}_p(a) = k$. Either $k = 1, 2, q, 2q$. If $k = 1$, we have $a \equiv 1\mod{p}$ which means $a^q + 1 \equiv 2\mod{p} \implies p = 2$ which is impossible. If $k = q$, we have $a^q + 1 \equiv 2\mod{p} \implies p = 2$, impossible. If $k = 2q$, since $a^{p - 1} \equiv 1\mod{p}$, we have $2q \mid p - 1$, however $p \leq q$ so it's impossible, which means $k = 2 \implies a^2 \equiv 1\mod{p} \implies p \mid (a - 1)(a + 1)$. If $p \mid a - 1$, $p = 2$, which means $p \mid a + 1$.