PermCheck Codility with time complexity of O(N)

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in \$1 \ldots N\$ exactly once.

I got 100% for it but I got a time complexity of \$O(N * log(N))\$ or \$O(N)\$. How could I make this code \$O(N)\$? Could you also give a brief description of what makes code \$O(N)\$?

Array.Sort(A);
if(A[0] == 1 && A.Length == 1) return 1;
if(A[0] != 1) return 0;

int n = 0;
for(int i = 0; i < A.Length; i++)
{    
    if(i < A.Length - 1)
    {
        if(A[i+1] == A[i] + 1)
        {
            n += 1;
        }
        else 
        {
            return 0;   
        }
    }
}
return 1;

This code involves sorting an array of \$N\$ elements, so it has \$O(N * log N)\$ time complexity. To achieve \$O(N)\$ time complexity, you need to avoid sorting input data. Instead, you can create an array of \$N\$ bools to check that each number from \$1\$ to \$N\$ is present in the input array.

StackExchange Code Review Q#69315, answer score: 10