My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <vector>
       
#include <algorithm>
       
 
       
// produce S1, S2, etc.

       
unsigned int pseudoRandom()
       
{
       
  static unsigned long long state = 290797;
       
  state *= state;
       
  state %= 50515093;
       
  return (unsigned int)state;
       
}
       
 
       
// basic O(n^2) algorithm, surprisingly fast for size = 10000

       
unsigned long long bruteForce(unsigned int size)
       
{
       
  // precompute all values
       
  std::vector<unsigned int> data = { 0 }; // dummy element to have S1,S2,... at positions 1,2,...
       
  for (unsigned int i = 1; i <= size; i++)
       
    data.push_back(pseudoRandom());
       
 
       
  // just a dumb scan over all intervals
       
  unsigned long long result = 0;
       
  for (unsigned int i = 1; i <= size; i++)
       
  {
       
    auto minimum = data[i];
       
    //for (unsigned int j = i; j <= size; j++)
       
    for (unsigned int j = i; j >= 1; j--) // same concept as above but going backwards
       
    {
       
      minimum = std::min(minimum, data[j]);
       
      result += minimum;
       
    }
       
  }
       
 
       
  return result;
       
}
       
 
       
// "number" is the smallest number from its "position" to the current position

       
struct Minimum
       
{
       
  unsigned int number;
       
  unsigned int position;
       
};
       
 
       
// almost O(n), about a minute for size = 2*10^9

       
unsigned long long search(unsigned int size)
       
{
       
  // basically a stack of all previous minimums
       
  std::vector<Minimum> best;
       
  // add an unused dummy element so that the stack never becomes empty
       
  best.push_back({ 0, 0 });
       
 
       
  unsigned long long result = 0;
       
  for (unsigned int i = 1; i <= size; i++)
       
  {
       
    // produce next pseudo-random number
       
    auto current = pseudoRandom();
       
 
       
    // remove all elements larger than the current one
       
    auto validUntil = i;
       
    while (best.back().number >= current)
       
    {
       
      validUntil = best.back().position;
       
      best.pop_back();
       
    }
       
 
       
    // the current value is at least the smallest value for a sequence of length 1 starting at i
       
    best.push_back({ current, validUntil });
       
 
       
    // add all sequences
       
    auto last = i + 1;
       
    for (unsigned int backwards = best.size() - 1; backwards > 0; backwards--)
       
    {
       
      // its the same minimum number for all those positions
       
      unsigned long long distance = last - best[backwards].position;
       
      result += distance * best[backwards].number;
       
 
       
      // update position
       
      last = best[backwards].position;
       
    }
       
  }
       
 
       
  return result;
       
}
       
 
       
int main()
       
{
       
//#define FIND_CYCLE

       
#ifdef  FIND_CYCLE
       
  auto first = pseudoRandom();
       
  unsigned int cycleLength = 0;
       
  while (pseudoRandom() != first)
       
    cycleLength++;
       
  std::cout << "cycle length: " << cycleLength << std::endl;
       
#else
       
  unsigned int limit = 2000000000;
       
  std::cin >> limit;
       
  //std::cout << bruteForce(limit) << std::endl;
       
  std::cout << search(limit) << std::endl;
       
#endif
       
 
       
  return 0;
       
}

This solution contains 14 empty lines, 17 comments and 6 preprocessor commands.