Solução escrita por Arthur Lobo
Conhecimento prévio necessário:
Considerando que $$i \le j$$ só existem 2 formatos diferentes que satisfazem a condição de ser interessante, vamos pensar em como contar cada uma delas:
$$A_i = i, A_j = j$$
Vamos chamar $$i$$ de legal se $$A_i = i$$. Qualquer par $$i,j$$ em que $$i< j$$ e ambos $$i$$ e $$j$$ são legais é um par interessante, pois o fato de $$A_i = i$$ torna $$i$$ meio “independente” de $$j$$.
Seja $$Q$$ a quantidade de índices legais. A quantidade de pares nesse formato vai ser $$Q*(Q-1)/2$$, porque podemos escolher quaisquer $$i,j$$ entre os que tal que $$i < j$$, e $$i$$ e $$j$$ são legais.
$$A_i = j, A_j = i$$
Para cada $$i$$, existe no máximo um $$j$$ que satisfaz essa condição. Então podemos fazer um for com $$i$$ indo de $$1$$ até $$N$$ checando 2 coisas: se $$A_i > i$$ e $$A_{A_i} = i$$ (ou seja, se $$A_j = i$$). Se ambas forem verdadeiras, aumentamos a resposta em 1, pois encontramos um par válido.
A primeira parte é $$O(N)$$ e a segunda também, então no final o a complexidade fica $$O(N)$$.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.