/*
  A non-empty array A consisting of N integers is given. A pair of
  integers (P, Q), such that 0 ≤ P < Q < N, is called a slice of array
  A (notice that the slice contains at least two elements). The
  average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q]
  divided by the length of the slice. To be precise, the average
  equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).
  

  For example, array A such that:

    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8


  contains the following example slices:

  slice (1, 2), whose average is (2 + 2) / 2 = 2;
  slice (3, 4), whose average is (5 + 1) / 2 = 3;
  slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.

  The goal is to find the starting position of a slice whose average is minimal.

  Write a function:

  int solution(vector<int> &A);

  that, given a non-empty array A consisting of N integers, returns
  the starting position of the slice with the minimal average. If
  there is more than one slice with a minimal average, you should
  return the smallest starting position of such a slice.
  

  For example, given array A such that:

    A[0] = 4
    A[1] = 2
    A[2] = 2
    A[3] = 5
    A[4] = 1
    A[5] = 5
    A[6] = 8

  the function should return 1, as explained above.

  Write an efficient algorithm for the following assumptions:

  N is an integer within the range [2..100,000]; each element of array
  A is an integer within the range [−10,000..10,000].
  
*/

#include <bits/stdc++.h>
using namespace std;

template <typename Container> void printC(Container& c)
{ for (auto i: c) { cout << i << " "; } cout << endl; };

class Solution
{
public:
    // array size is in range [2..100,000]
    int solution(vector<int>& A)
    {
        int startPos = 0;
        double minAvg = DBL_MAX;
        cout << setw(10) << "input: "; printC(A);
        int maxWindowSize = A.size() == 2 ? 2 : 3; // minAvg slice occurs in slices of length 2 or 3
        for (int windowSize = 2; windowSize <= maxWindowSize; windowSize++)
        {
            cout << "windowSize: " << windowSize << endl;
            double sum = 0;
            deque<int> que; // que with sliding window values
            for (int i = 0; i < windowSize; i++)
            {
                sum += A.at(i);
                que.push_front(A.at(i));
            }
            double windowAvg = sum / windowSize;
            
            cout << setw(10) << "que: "; printC(que);
            cout << setw(10) << "sum: " << sum << " windowAvg: " << setprecision(2) << fixed << windowAvg << endl;
            if (windowAvg < minAvg) cout << setw(27) << "new minAvg: startPos: " << startPos << " windowAvg: " << setprecision(2) << fixed << windowAvg << endl;
                    
            minAvg = min(minAvg, windowAvg);
            
            for (int i = windowSize; i < (int)A.size(); i++)
            {
                sum -= que.back(); // A.at(i-windowSize)
                que.pop_back();
                que.push_front(A.at(i));
                sum += que.front(); // A.at(i)
                windowAvg = sum / windowSize;
                if (windowAvg < minAvg)
                {
                    startPos = i - windowSize + 1;
                    
                    cout << setw(27) << "new minAvg: startPos: " << startPos << " i: " << i << " minAvg: " << minAvg << " windowAvg: " << setprecision(2) << fixed << windowAvg << endl;
                    cout << setw(10) << "que: "; printC(que);
                    cout << setw(10) << "-------\n";
                    
                    minAvg = windowAvg;
                }
            }
        }
        return startPos;
    }
};

int main(void)
{
    vector<tuple<vector<int>,int>> testCases = {
        { {4,2,2,5,1,5,8},  1 },
        { {10,11,1,1,-1,2}, 3 },
        { {-5,-4,-3,-2,-1}, 0 },
        { {22,-1,0,-1}, 1 },
    };

    for (auto tc: testCases)
    {
        Solution s;
        vector<int>& input = get<0>(tc);
        int expected = get<1>(tc);
        int result = s.solution(input);
        
        int width = 10;
        cout << setw(width) << "input: "; printC(input);
        cout << setw(width) << "result: " << result << endl;    
        cout << setw(width) << "expected: " << expected << endl;
        cout << (result == expected ? "\033[32m" "passed" "\033[0m" : "\033[31m" "failed" "\033[0m") << endl;
        cout << "----------------------------\n";
    }
}