import java.io.*;
import java.util.*;


public class Main {

    private static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static final PrintWriter out = new PrintWriter(System.out);
    private static final StreamTokenizer tok = new StreamTokenizer(in);

    public static void main(String[] args) throws IOException
    {
        int windowSize = nextInt();
        Queue<Integer> q = new LinkedList<Integer>();
        Deque<Integer> maxQ = new LinkedList<Integer>();
        while(true)
        {
            Integer n = nextInt();
            if(n == -1)
                break;
            q.add(n);
            while((maxQ.isEmpty() == false) && (maxQ.peekLast() < n))
                maxQ.removeLast();
            maxQ.add(n);
            if(q.size() == windowSize)
            {
                Integer elemToRemove = q.remove();
                Integer maxElement = maxQ.peek();
                out.println(maxElement);
                if(maxElement == elemToRemove)
                    maxQ.remove();
            }
        }
        out.flush();
    }

    private static int nextInt() throws IOException
    {
        if(tok.nextToken() != StreamTokenizer.TT_NUMBER)
            throw new IOException();
        return (int)tok.nval;
    }

}

//note, though there's while loop to remove elements from maxQ,
//amortized comlexity is still O(n)

It's quite a beautiful solution!! Tks you

Here is a c++ variation on this Java solution:

int main()
{
  int m;
  cin >> m;

  int n = 0;
  int a[25001] = {};
  for (;; n++)
  {
    cin >> a[n];
    if (a[n] == -1)
      break;
  }

  int r = 0;
  int max_a[25001] = {};
  for (int i = 0; i < m - 1; i++, r++)
  {
    while (r - 1 >= 0 && max_a[r - 1] < a[i])
      r--;

    max_a[r] = a[i];
  }

  int l = 0;
  for (int i = m - 1; i < n; i++, r++)
  {
    while (r - 1 >= l && max_a[r - 1] < a[i])
      r--;

    max_a[r] = a[i];

    cout << max_a[l] << '\n';

    int j = i - m + 1;
    if (a[j] == max_a[l])
      l++;
  }
}

Note: I am not using any of the data structures