import java.util.Random;

public class numtest {
   public class CycleQueue {
	   //очередь
	   double[] a;
	   int write_point;
	   int count;
	   int block_size,block_count;
	   boolean first_cycle;
	   
	   boolean global_is_min_max;
	   double global_min;
	   double global_max;
	   double global_sum;
	   	   
	   // для каждого блока в 100 чисел - локальный минимакс 
	   double[] loc_min;
	   double[] loc_max;
	   boolean[] is_min_max;
	   double[] loc_sum;
	   
	   
	   public CycleQueue(int p_block_size, int p_block_count) {
		 write_point=0;
		 block_size= p_block_size;
		 block_count =p_block_count;
		 a=new double[block_size*block_count+10];
		 loc_min=new double[block_count+2];
		 loc_max=new double[block_count+2];
		 loc_sum=new double[block_count+2];
		 is_min_max=new boolean[block_count+2];
		 first_cycle=true;

		 global_is_min_max=false;
		 global_min=0;
		 global_max=0;
		 global_sum=0;
		 
		 write_point=0;
		 count=0;
		 for (int i=0 ; i<block_count; i++){
			   is_min_max[i]=false;
			   loc_min[i]=0;
			   loc_max[i]=0;
		 }
	   }
	   
	   public void PutNum (double n) {
		 int block_no=write_point / block_size;
		// System.out.println(block_no);
		 // проверим, не совпадает ли затираемое с минимаксом
		 boolean do_recalc_minmax=(!first_cycle) &&
			 (a[write_point]==loc_min[block_no] || 
			  a[write_point]==loc_max[block_no] );
		 
		 //если затираем старое значение - выкинем из суммы по блоку
		 if (!first_cycle) {
			  loc_sum[block_no]-=a[write_point];
			  global_sum-=a[write_point];
			  }
		 a[write_point]=n;
		 
		 loc_sum[block_no]+=n;
		 global_sum+=n;
		 
		 boolean local_extremum_changed=false;
		 
		 // минимакс по блоку не считался
		 if (!is_min_max[block_no]) {
			 is_min_max[block_no]=true; 
			 loc_min[block_no]=n;
			 loc_max[block_no]=n;
			 local_extremum_changed=true;
		 }
		
		 // локальный экстремум не затерт
		 if (!do_recalc_minmax) {
			    if (n<loc_min[block_no]) {
				      loc_min[block_no]=n;
				      local_extremum_changed=true;
				   }
			    if (n>loc_max[block_no]) {
				      loc_max[block_no]=n;
				      local_extremum_changed=true;
				   }
		 } else {
			    // минимакс блока затерт, пересчитаем
				int from=block_no*block_size;
				int to=block_no*block_size+1;
				//Блок заполнен не полностью?
				if (to>count-1) {to=count-1;};
				double mn=a[from];
				double mx=a[from];
				for (int i=from;i<=to; i++) {
					if (a[i]<mn) mn=a[i];
					if (a[i]<mx) mx=a[i];
				}
				
  		        local_extremum_changed=
  		        	loc_max[block_no]!=mx ||
				    loc_min[block_no]!=mn;
				loc_max[block_no]=mx;
				loc_min[block_no]=mn;
		 }
		 
		 // если поменялся экстремум блока, пропишем его в глобальный
		 if (local_extremum_changed) {
			// минимакса не было 
			if (!global_is_min_max) {
				global_is_min_max=true;
				global_min=loc_min[block_no];
				global_max=loc_max[block_no];
			} 
			if (loc_min[block_no]<global_min) {
				global_min=loc_min[block_no];
			}
			if (loc_max[block_no]>global_max) {
				global_max=loc_max[block_no];
			}
		 }
		 if (write_point==block_size*block_count-1) 
		   {write_point= 0; 
		    first_cycle=false;
		   } 
		 else write_point++;
		 
		 if (count<block_size*block_count) count++; 
	   }
	   
   }
   
   void Test() {	   
	   Random gen=new Random();
	   CycleQueue q=new CycleQueue(100,100);
	   
	   long t_strt=System.currentTimeMillis();
	   for (int i=0;i<1000000;i++)
	     {q.PutNum(gen.nextDouble());
		   
	     }
	   System.out.print((System.currentTimeMillis()-t_strt));
	   double s=0;
	   double mn=0;
	   double mx=0;
	   mn=q.a[0];
	   mx=q.a[0];
	   for(int i=0; i<q.count; i++) {
		   s+=q.a[i];
		   if (mn>q.a[i]) mn=q.a[i];
		   if (mx<q.a[i]) mx=q.a[i];
	   };
	   System.out.print("\n Сумма ");
	   System.out.print(q.global_sum);
	   
	   double s1=0;
	   for(int i=0; i<q.block_count; i++) {
		   s1+=q.loc_sum[i];
	   }
	   System.out.print("\n Сумма1 ");
	   System.out.print(s1);

	   System.out.print("\n Сумма пересч ");
	   System.out.print(s);

	   System.out.print("\n Макс ");
	   System.out.print(q.global_max);

	   System.out.print("\n Макс пересч");
	   System.out.print(mx);

	   System.out.print("\n Мin ");
	   System.out.print(q.global_min);

	   System.out.print("\n Мin пересч");
	   System.out.print(mn);
	   
   }
   
   static public void main(String[] argv) {
	     
	   numtest n=new numtest();
	   n.Test();
	   
   }
}