int FirstMissingPositive(int A[], int n) 
{
    int i = 0;
    while (i < n)
    {
        int ai = A[i];

        //find the position for each element, kind like sort it, but much fast
        if (0 <= ai && ai < n)
            if (A[ai] != ai)//prevent from infinit swap
            {
                A[i] = A[ai];
                A[ai] = ai;
                continue;
            }

        ++i;
    }

    i = 1;
    while(i < n && A[i] == i) i++;
	
	//fisrt element maybe n, if so, the largest missed positive number should be n+1
	if (A[0] == i) ++i;

    return i;
}

#include <stdio.h>

int main(int argc, char** argv)
{
    int a[] = {3,4,-1,1};
    int n = sizeof(a)/sizeof(int);

    printf("%d\n", FirstMissingPositive(a, n));
    
    int b[] = {100,95,97,12,93,6,92,90,58,86,
        67,64,85,82,80,62,75,79,78,31,
        65,14,59,19,71,70,52,13,33,35,
        10,44,40,9,2,39,50,28,22,46,
        48,45,54,53,49,20,51,60,4,41,
        32,83,24,57,38,42,17,29,23,34,
        66,43,55,21,30,26,11,27,5,61,
        68,84,63,72,25,36,73,56,76,1,
        3,47,16,81,7,37,15,74,77,87,
        89,8,18,88,69,91,96,94,98,99};
    n = sizeof(b)/sizeof(int);
    printf("%d\n", FirstMissingPositive(b, n));

    return 0;
}