// bounded-capacity FIFO queue, safe for use by multiple threads.
class Queue {

  int c;        // capacity of queue
  int[] q;      // contents of queue
  int first=0;  // index of element at head of queue
  int n=0;      // number of elements in queue

  Queue(int c1) { 
    c=c1; 
    q = new int[c];
  }

  synchronized void insert(int i) {
    while (n==c) {
      try { wait(); } 
      catch (InterruptedException e) {}
    }
    q[(first+n)%c] = i;
    n++;
    // if a thread might be waiting to remove an element, wake everyone up.
    if (n==1) notifyAll();
  }

  synchronized int remove() {
    while (n==0) {
      try { wait(); } 
      catch (InterruptedException e) {}
    }
    int i = q[first];
    first++;
    n--;
    // if a thread might be waiting to insert an element, wake everyone up.
    if (n==c-1) notifyAll();
    return i;
  }
}