using System;
using System.Collections.Generic;
using System.Linq;

namespace yield {
    public static class MovingMaxTask {
        //структура элемента последовательности, включающая значение и номер в последовательности
        private struct SequenceElement {
            public int Number {
                get; private set;
            }
            public DataPoint Value {
                get; private set;
            }

            public SequenceElement(int number, DataPoint value) {
                Number = number;
                Value = value;
            }
        }

        public static IEnumerable<DataPoint> MovingMax(this IEnumerable<DataPoint> data, int windowWidth) {
            //Используем дек (Deque), в котором хранятся структуры (значение, номер)
            //Если номер переднего элемента очереди — тот, что уходит из окна, то удаляем его из начала очереди.
            //Удаляем из конца очереди элементы, значение которых меньше, чем у новодобавляемого (они уже не максимумы)
            //Вставляем новый элемент в конец очереди
            //Максимум на каждом шаге — в начале очереди.
            //Время амортизированное O(1).
            Deque<SequenceElement> sequence = new Deque<SequenceElement>();
            int index = 0;
            foreach (DataPoint point in data) {
                index++;
                if (index > windowWidth) {
                    if (sequence.GetHeadValue().Number <= index - windowWidth) {
                        sequence.RemoveHead();
                    }
                }
                while(sequence.Count > 0 && sequence.GetTailValue().Value.OriginalY < point.OriginalY) {
                    sequence.RemoveTail();
                }
                sequence.AddTail(new SequenceElement(index, point));
                point.MaxY = sequence.GetHeadValue().Value.OriginalY;
                yield return point;
            }
        }
    }


    public class Deque<T> {//Самописная двусторонняя очередь на связных списках
        public class DequeElement<T> {
            public DequeElement<T> Next {
                get; set;
            }

            public DequeElement<T> Prev {
                get; set;
            }

            public T Value;

            public DequeElement(T value) {
                Value = value;
            }
        }

        private DequeElement<T> head;
        private DequeElement<T> tail;

        public int Count {
            get; private set;
        }

        public void AddHead(T value) {
            if (Count == 0) {
                head = new DequeElement<T>(value);
                tail = head;
            }
            else {
                head.Next = new DequeElement<T>(value);
                head.Next.Prev = head;
                head = head.Next;
            }
            Count++;
        }

        public void AddTail(T value) {
            if (Count == 0) {
                head = new DequeElement<T>(value);
                tail = head;
            }
            else {
                tail.Prev = new DequeElement<T>(value);
                tail.Prev.Next = tail;
                tail = tail.Prev;
            }
            Count++;
        }

        public T RemoveHead() {
            if (Count == 0) {
                throw new Exception("Deque is empty");
            }
            T value = head.Value;
            if (Count > 1) {
                head.Prev.Next = null;
                head = head.Prev;
            }
            Count--;
            return value;
        }

        public T RemoveTail() {
            if (Count == 0) {
                throw new Exception("Deque is empty");
            }
            T value = tail.Value;
            if (Count > 1) {
                tail.Next.Prev = null;
                tail = tail.Next;
            }
            Count--;
            return value;
        }

        public T GetHeadValue() {
            if (Count == 0) {
                throw new Exception("Deque is empty");
            }
            return head.Value;
        }

        public T GetTailValue() {
            if (Count == 0) {
                throw new Exception("Deque is empty");
            }
            return tail.Value;
        }
    }
}