#include <iostream>
#include "data.h" // arr, N, SQRT_N, INF

using namespace std;

int sq[SQRT_N]; 

int rmq(int l, int r) {
  int i;
  int res = INF;

  //part before we hit the first big block
  for (i = l; i % SQRT_N != 0; i++)
    res = min(res, arr[i]);
  //iterate over all the blocks contained in [l,r]
  for (; i + (SQRT_N-1) <= r; i += SQRT_N)
    res = min(res, sq[i/SQRT_N]);
  //after the last block
  for (; i <= r; i++)
    res = min(res, arr[i]);
  return res;
}

int main() {
	printArr();

	//setup sqrt table
  for (int k = 0; k < SQRT_N; k++)
    sq[k] = INF;
	for (int i = 0; i < N; i++) 
    sq[i/SQRT_N] = min(sq[i/SQRT_N], arr[i]);
	
  int rmq_min = rmq(3, 7);
	int naive_min = arr[3];
	
	for (int i = 3; i <= 7; i++)
		naive_min = min(naive_min, arr[i]);
	
	cout << "min(a[3], ..., a[7]) = " << rmq_min << endl;
	cout << (rmq_min == naive_min ? "Correct!" : "Incorrect!") << endl;
		
	return 0;
}
