Minimum Unobtainable Sum with Statistical Elimination

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using System.Threading;

namespace MinimumUnobtainableSum
{
    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch s = Stopwatch.StartNew();
            Random r = new Random();
            int N = 100000; // r.Next(100000);
            int M = 100000; // r.Next(100000);

            int[] S = new int[N];
            bool oneExists = false;
            for (int i = 0; i < N; i++)
            {
                S[i] = r.Next(1000000000);
                if (S[i] == 1)
                    oneExists = true;
            }

            if (!oneExists)
            {
                //all results 1
                s.Stop();
                Console.WriteLine("N: {0}, M: {1}, time: {2}", N, M, s.Elapsed.ToString());
                Console.ReadKey();
                return;
            }

            int[,] Queries = new int[M, 2];
            for (int i = 0; i < M; i++)
            {
                Queries[i, 0] = r.Next(N - 1);
                Queries[i, 1] = r.Next(N - 1);
                if (Queries[i, 0] > Queries[i, 1])
                {
                    int temp = Queries[i, 1];
                    Queries[i, 1] = Queries[i, 0];
                    Queries[i, 0] = temp;
                }
            }

            int[] results = new int[M];


            var result = Parallel.For(0, M, i =>
            {
                var d = Queries[i, 1] - Queries[i, 0];
                if (d <= 0)
                    return;
                int[] subS = new int[d + 1];
                bool one_exists = false;
                for (int k = 0, j = Queries[i, 0]; j <= Queries[i, 1]; j++, k++)
                {
                    subS[k] = S[j];
                    if (subS[k] == 1)
                        one_exists = true;
                }

                if (!one_exists)
                {
                    results[i] = 1;
                    return;
                }

                subS = subS.OrderBy(x => x).ToArray();

                results[i] = Calculate(subS);
            });

            s.Stop();
            Console.WriteLine("N: {0}, M: {1}, time: {2}", N, M, s.Elapsed.ToString());
            Console.ReadKey();
        }

        static int Calculate(int[] S)
        {
            int max = 0;
            for (int i = 0; i < S.Length; i++)
            {
                if (S[i] <= max + 1)
                    max = max + S[i];
                else
                    return max + 1;
            }
            return max + 1;
        }
    }
}