using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApp
{
    public class RingBuffer<T> : IEnumerable<T>
    {
        #region フィールド
        T[] data;
        int _Count;
        #endregion
 
        #region コンストラクター
        /// <summary>
        /// 初期最大容量を指定して初期化
        /// </summary>
        /// <param name="capacity">初期載大容量</param>
        public RingBuffer(int capacity)
        {
            this.data = new T[capacity];
        }
 
        public RingBuffer(IList<T> list)
        {
            this.data = list.ToArray<T>();
            _Count = data.Length;
        }
        #endregion
 
        #region プロパティー
 
        public int Count
        {
            get
            {
                return _Count;
            }
        }
 
        /// <summary>
        /// インデクサー
        /// </summary>
        /// <param name="i">読み書き位置</param>
        /// <returns>読み出した要素</returns>
        public T this[int i]
        {
            get
            {
                if (i < 0)
                {
                    uint a = (uint)-i;
                    if (a > _Count)
                    {
                        a = MathEx.mod(a, (uint)_Count);
                        if (a == 0) return data[0];
                    }
                    return data[_Count - a];
                }
                return this.data[(int)MathEx.mod((uint)i, (uint)data.Length)];
            }
            set
            {
                this.data[(int)MathEx.mod((uint)i, (uint)data.Length)] = value;
            }
        }
 
        #endregion
 
        #region 配列操作
        /// <summary>
        /// 配列を拡張する
        /// </summary>
        /// <param name="capacity"></param>
        private void Extend(int capacity)
        {
            if ( capacity <= _Count)
                throw new ArgumentException("容量が要素の数より少ないか、同じ");
 
            Array.Resize(ref data, capacity);
        }
        /// <summary>
        /// 配列の大きさを要素の個数に合わせる
        /// </summary>
        public void Fit()
        {
            Array.Resize(ref data, _Count);
        }
        /// <summary>
        /// idx番目の位置に新しい要素を追加
        /// </summary>
        /// <param name="idx">追加位置</param>
        /// <param name="elem">追加する要素</param>
        public void Insert(int idx, T elem)
        {
            if (this._Count <= this.data.Length - 1)
                Extend(_Count + 1);
 
            Array.Copy(data, idx, data, idx + 1, _Count - idx);
            data[idx] = elem;
            _Count++;
        }
 
        /// <summary>
        /// 先頭に新しい要素を追加。
        /// </summary>
        /// <param name="elem">追加する要素</param>
        public void InsertFirst(T elem)
        {
            this.Insert(0, elem);
        }
 
        /// <summary>
        /// 末尾に新しい要素を追加。
        /// </summary>
        /// <param name="elem">追加する要素</param>
        public void InsertLast(T elem)
        {
            if (this._Count <= this.data.Length - 1)
                Extend(_Count + 1);
            data[_Count] = elem;
            _Count++;
        }
 
        /// <summary>
        /// i 番目の要素を削除。
        /// </summary>
        /// <param name="i">削除位置</param>
        public void Delete(int idx)
        {
 
            for (int n = idx; n < this._Count - 1; n++)
            {
                data[n] = data[n + 1];
            }
 
            _Count--;
        }
 
        /// <summary>
        /// 先頭の要素を削除。
        /// </summary>
        public void DeleteFirst()
        {
            //this.top = (this.top + 1) & this.mask;
            Delete(0);
        }
 
        /// <summary>
        /// 末尾の要素を削除。
        /// </summary>
        public void DeleteLast()
        {
            //this.bottom = (this.bottom - 1) & this.mask;
            Delete(_Count - 1);
        }
 
        #endregion
 
        #region 検索
        public int FindIndex(Predicate<T> match)
        {
            for (int idx = 0; idx < data.Length; idx++)
            {
                if (match(data[idx]))
                    return idx;
            }
            return -1;
        }
 
        public int FindIndex(int startIndex, Predicate<T> match)
        {
            for (int idx = startIndex; idx < data.Length; idx++)
            {
                if (match(data[idx]))
                    return idx;
            }
            return -1;
        }
 
        public int FindIndex(int startIndex, int count, Predicate<T> match)
        {
            for (int idx = startIndex; idx < startIndex + count; idx++)
            {
                if (match(data[idx]))
                    return idx;
            }
            return -1;
        }
        #endregion
 
        #region IEnumerable<T> メンバ
 
        public IEnumerator<T> GetEnumerator()
        {
            for (int i = 0; i < _Count; i++)
            {
                yield return data[i];
            }
        }
 
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }
 
        #endregion
    }
}
 
public static class MathEx
{
    /// <summary>
    /// 剰余の計算
    /// </summary>
    /// <param name="x">割られる数</param>
    /// <param name="y">割る数</param>
    /// <returns>余り</returns>
    public static uint mod(uint x, uint y)
    {
        ulong a = x;
        ulong b = y;
        b = b << 31;
        for (int i = 0; i < 32; i++)
        {
            if (a >= b)
            {
                a -= b;
            }
            b = b >> 1;
        }
        return (uint)a;
    }
}

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgQ29uc29sZUFwcAp7CiAgICBwdWJsaWMgY2xhc3MgUmluZ0J1ZmZlcjxUPiA6IElFbnVtZXJhYmxlPFQ+CiAgICB7CiAgICAgICAgI3JlZ2lvbiDjg5XjgqPjg7zjg6vjg4kKICAgICAgICBUW10gZGF0YTsKICAgICAgICBpbnQgX0NvdW50OwogICAgICAgICNlbmRyZWdpb24KCiAgICAgICAgI3JlZ2lvbiDjgrPjg7Pjgrnjg4jjg6njgq/jgr/jg7wKICAgICAgICAvLy8gPHN1bW1hcnk+CiAgICAgICAgLy8vIOWIneacn+acgOWkp+WuuemHj+OCkuaMh+WumuOBl+OBpuWIneacn+WMlgogICAgICAgIC8vLyA8L3N1bW1hcnk+CiAgICAgICAgLy8vIDxwYXJhbSBuYW1lPSJjYXBhY2l0eSI+5Yid5pyf6LyJ5aSn5a656YePPC9wYXJhbT4KICAgICAgICBwdWJsaWMgUmluZ0J1ZmZlcihpbnQgY2FwYWNpdHkpCiAgICAgICAgewogICAgICAgICAgICB0aGlzLmRhdGEgPSBuZXcgVFtjYXBhY2l0eV07CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHB1YmxpYyBSaW5nQnVmZmVyKElMaXN0PFQ+IGxpc3QpCiAgICAgICAgewogICAgICAgICAgICB0aGlzLmRhdGEgPSBsaXN0LlRvQXJyYXk8VD4oKTsKICAgICAgICAgICAgX0NvdW50ID0gZGF0YS5MZW5ndGg7CiAgICAgICAgfQogICAgICAgICNlbmRyZWdpb24KCiAgICAgICAgI3JlZ2lvbiDjg5fjg63jg5Hjg4bjgqPjg7wKCiAgICAgICAgcHVibGljIGludCBDb3VudAogICAgICAgIHsKICAgICAgICAgICAgZ2V0CiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHJldHVybiBfQ291bnQ7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIC8vLyA8c3VtbWFyeT4KICAgICAgICAvLy8g44Kk44Oz44OH44Kv44K144O8CiAgICAgICAgLy8vIDwvc3VtbWFyeT4KICAgICAgICAvLy8gPHBhcmFtIG5hbWU9ImkiPuiqreOBv+abuOOBjeS9jee9rjwvcGFyYW0+CiAgICAgICAgLy8vIDxyZXR1cm5zPuiqreOBv+WHuuOBl+OBn+imgee0oDwvcmV0dXJucz4KICAgICAgICBwdWJsaWMgVCB0aGlzW2ludCBpXQogICAgICAgIHsKICAgICAgICAgICAgZ2V0CiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChpIDwgMCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICB1aW50IGEgPSAodWludCktaTsKICAgICAgICAgICAgICAgICAgICBpZiAoYSA+IF9Db3VudCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIGEgPSBNYXRoRXgubW9kKGEsICh1aW50KV9Db3VudCk7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmIChhID09IDApIHJldHVybiBkYXRhWzBdOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICByZXR1cm4gZGF0YVtfQ291bnQgLSBhXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIHJldHVybiB0aGlzLmRhdGFbKGludClNYXRoRXgubW9kKCh1aW50KWksICh1aW50KWRhdGEuTGVuZ3RoKV07CiAgICAgICAgICAgIH0KICAgICAgICAgICAgc2V0CiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHRoaXMuZGF0YVsoaW50KU1hdGhFeC5tb2QoKHVpbnQpaSwgKHVpbnQpZGF0YS5MZW5ndGgpXSA9IHZhbHVlOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAjZW5kcmVnaW9uCgogICAgICAgICNyZWdpb24g6YWN5YiX5pON5L2cCiAgICAgICAgLy8vIDxzdW1tYXJ5PgogICAgICAgIC8vLyDphY3liJfjgpLmi6HlvLXjgZnjgosKICAgICAgICAvLy8gPC9zdW1tYXJ5PgogICAgICAgIC8vLyA8cGFyYW0gbmFtZT0iY2FwYWNpdHkiPjwvcGFyYW0+CiAgICAgICAgcHJpdmF0ZSB2b2lkIEV4dGVuZChpbnQgY2FwYWNpdHkpCiAgICAgICAgewogICAgICAgICAgICBpZiAoIGNhcGFjaXR5IDw9IF9Db3VudCkKICAgICAgICAgICAgICAgIHRocm93IG5ldyBBcmd1bWVudEV4Y2VwdGlvbigi5a656YeP44GM6KaB57Sg44Gu5pWw44KI44KK5bCR44Gq44GE44GL44CB5ZCM44GYIik7CgogICAgICAgICAgICBBcnJheS5SZXNpemUocmVmIGRhdGEsIGNhcGFjaXR5KTsKICAgICAgICB9CiAgICAgICAgLy8vIDxzdW1tYXJ5PgogICAgICAgIC8vLyDphY3liJfjga7lpKfjgY3jgZXjgpLopoHntKDjga7lgIvmlbDjgavlkIjjgo/jgZvjgosKICAgICAgICAvLy8gPC9zdW1tYXJ5PgogICAgICAgIHB1YmxpYyB2b2lkIEZpdCgpCiAgICAgICAgewogICAgICAgICAgICBBcnJheS5SZXNpemUocmVmIGRhdGEsIF9Db3VudCk7CiAgICAgICAgfQogICAgICAgIC8vLyA8c3VtbWFyeT4KICAgICAgICAvLy8gaWR455Wq55uu44Gu5L2N572u44Gr5paw44GX44GE6KaB57Sg44KS6L+95YqgCiAgICAgICAgLy8vIDwvc3VtbWFyeT4KICAgICAgICAvLy8gPHBhcmFtIG5hbWU9ImlkeCI+6L+95Yqg5L2N572uPC9wYXJhbT4KICAgICAgICAvLy8gPHBhcmFtIG5hbWU9ImVsZW0iPui/veWKoOOBmeOCi+imgee0oDwvcGFyYW0+CiAgICAgICAgcHVibGljIHZvaWQgSW5zZXJ0KGludCBpZHgsIFQgZWxlbSkKICAgICAgICB7CiAgICAgICAgICAgIGlmICh0aGlzLl9Db3VudCA8PSB0aGlzLmRhdGEuTGVuZ3RoIC0gMSkKICAgICAgICAgICAgICAgIEV4dGVuZChfQ291bnQgKyAxKTsKCiAgICAgICAgICAgIEFycmF5LkNvcHkoZGF0YSwgaWR4LCBkYXRhLCBpZHggKyAxLCBfQ291bnQgLSBpZHgpOwogICAgICAgICAgICBkYXRhW2lkeF0gPSBlbGVtOwogICAgICAgICAgICBfQ291bnQrKzsKICAgICAgICB9CgogICAgICAgIC8vLyA8c3VtbWFyeT4KICAgICAgICAvLy8g5YWI6aCt44Gr5paw44GX44GE6KaB57Sg44KS6L+95Yqg44CCCiAgICAgICAgLy8vIDwvc3VtbWFyeT4KICAgICAgICAvLy8gPHBhcmFtIG5hbWU9ImVsZW0iPui/veWKoOOBmeOCi+imgee0oDwvcGFyYW0+CiAgICAgICAgcHVibGljIHZvaWQgSW5zZXJ0Rmlyc3QoVCBlbGVtKQogICAgICAgIHsKICAgICAgICAgICAgdGhpcy5JbnNlcnQoMCwgZWxlbSk7CiAgICAgICAgfQoKICAgICAgICAvLy8gPHN1bW1hcnk+CiAgICAgICAgLy8vIOacq+WwvuOBq+aWsOOBl+OBhOimgee0oOOCkui/veWKoOOAggogICAgICAgIC8vLyA8L3N1bW1hcnk+CiAgICAgICAgLy8vIDxwYXJhbSBuYW1lPSJlbGVtIj7ov73liqDjgZnjgovopoHntKA8L3BhcmFtPgogICAgICAgIHB1YmxpYyB2b2lkIEluc2VydExhc3QoVCBlbGVtKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKHRoaXMuX0NvdW50IDw9IHRoaXMuZGF0YS5MZW5ndGggLSAxKQogICAgICAgICAgICAgICAgRXh0ZW5kKF9Db3VudCArIDEpOwogICAgICAgICAgICBkYXRhW19Db3VudF0gPSBlbGVtOwogICAgICAgICAgICBfQ291bnQrKzsKICAgICAgICB9CgogICAgICAgIC8vLyA8c3VtbWFyeT4KICAgICAgICAvLy8gaSDnlarnm67jga7opoHntKDjgpLliYrpmaTjgIIKICAgICAgICAvLy8gPC9zdW1tYXJ5PgogICAgICAgIC8vLyA8cGFyYW0gbmFtZT0iaSI+5YmK6Zmk5L2N572uPC9wYXJhbT4KICAgICAgICBwdWJsaWMgdm9pZCBEZWxldGUoaW50IGlkeCkKICAgICAgICB7CiAgICAgICAgICAgIAogICAgICAgICAgICBmb3IgKGludCBuID0gaWR4OyBuIDwgdGhpcy5fQ291bnQgLSAxOyBuKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGRhdGFbbl0gPSBkYXRhW24gKyAxXTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgX0NvdW50LS07CiAgICAgICAgfQoKICAgICAgICAvLy8gPHN1bW1hcnk+CiAgICAgICAgLy8vIOWFiOmgreOBruimgee0oOOCkuWJiumZpOOAggogICAgICAgIC8vLyA8L3N1bW1hcnk+CiAgICAgICAgcHVibGljIHZvaWQgRGVsZXRlRmlyc3QoKQogICAgICAgIHsKICAgICAgICAgICAgLy90aGlzLnRvcCA9ICh0aGlzLnRvcCArIDEpICYgdGhpcy5tYXNrOwogICAgICAgICAgICBEZWxldGUoMCk7CiAgICAgICAgfQoKICAgICAgICAvLy8gPHN1bW1hcnk+CiAgICAgICAgLy8vIOacq+WwvuOBruimgee0oOOCkuWJiumZpOOAggogICAgICAgIC8vLyA8L3N1bW1hcnk+CiAgICAgICAgcHVibGljIHZvaWQgRGVsZXRlTGFzdCgpCiAgICAgICAgewogICAgICAgICAgICAvL3RoaXMuYm90dG9tID0gKHRoaXMuYm90dG9tIC0gMSkgJiB0aGlzLm1hc2s7CiAgICAgICAgICAgIERlbGV0ZShfQ291bnQgLSAxKTsKICAgICAgICB9CgogICAgICAgICNlbmRyZWdpb24KCiAgICAgICAgI3JlZ2lvbiDmpJzntKIKICAgICAgICBwdWJsaWMgaW50IEZpbmRJbmRleChQcmVkaWNhdGU8VD4gbWF0Y2gpCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGludCBpZHggPSAwOyBpZHggPCBkYXRhLkxlbmd0aDsgaWR4KyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChtYXRjaChkYXRhW2lkeF0pKQogICAgICAgICAgICAgICAgICAgIHJldHVybiBpZHg7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgcmV0dXJuIC0xOwogICAgICAgIH0KCiAgICAgICAgcHVibGljIGludCBGaW5kSW5kZXgoaW50IHN0YXJ0SW5kZXgsIFByZWRpY2F0ZTxUPiBtYXRjaCkKICAgICAgICB7CiAgICAgICAgICAgIGZvciAoaW50IGlkeCA9IHN0YXJ0SW5kZXg7IGlkeCA8IGRhdGEuTGVuZ3RoOyBpZHgrKykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKG1hdGNoKGRhdGFbaWR4XSkpCiAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGlkeDsKICAgICAgICAgICAgfQogICAgICAgICAgICByZXR1cm4gLTE7CiAgICAgICAgfQoKICAgICAgICBwdWJsaWMgaW50IEZpbmRJbmRleChpbnQgc3RhcnRJbmRleCwgaW50IGNvdW50LCBQcmVkaWNhdGU8VD4gbWF0Y2gpCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGludCBpZHggPSBzdGFydEluZGV4OyBpZHggPCBzdGFydEluZGV4ICsgY291bnQ7IGlkeCsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZiAobWF0Y2goZGF0YVtpZHhdKSkKICAgICAgICAgICAgICAgICAgICByZXR1cm4gaWR4OwogICAgICAgICAgICB9CiAgICAgICAgICAgIHJldHVybiAtMTsKICAgICAgICB9CiAgICAgICAgI2VuZHJlZ2lvbgoKICAgICAgICAjcmVnaW9uIElFbnVtZXJhYmxlPFQ+IOODoeODs+ODkAoKICAgICAgICBwdWJsaWMgSUVudW1lcmF0b3I8VD4gR2V0RW51bWVyYXRvcigpCiAgICAgICAgewogICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IF9Db3VudDsgaSsrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB5aWVsZCByZXR1cm4gZGF0YVtpXTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgU3lzdGVtLkNvbGxlY3Rpb25zLklFbnVtZXJhdG9yIFN5c3RlbS5Db2xsZWN0aW9ucy5JRW51bWVyYWJsZS5HZXRFbnVtZXJhdG9yKCkKICAgICAgICB7CiAgICAgICAgICAgIHJldHVybiB0aGlzLkdldEVudW1lcmF0b3IoKTsKICAgICAgICB9CgogICAgICAgICNlbmRyZWdpb24KICAgIH0KfQoKcHVibGljIHN0YXRpYyBjbGFzcyBNYXRoRXgKewogICAgLy8vIDxzdW1tYXJ5PgogICAgLy8vIOWJsOS9meOBruioiOeulwogICAgLy8vIDwvc3VtbWFyeT4KICAgIC8vLyA8cGFyYW0gbmFtZT0ieCI+5Ymy44KJ44KM44KL5pWwPC9wYXJhbT4KICAgIC8vLyA8cGFyYW0gbmFtZT0ieSI+5Ymy44KL5pWwPC9wYXJhbT4KICAgIC8vLyA8cmV0dXJucz7kvZnjgoo8L3JldHVybnM+CiAgICBwdWJsaWMgc3RhdGljIHVpbnQgbW9kKHVpbnQgeCwgdWludCB5KQogICAgewogICAgICAgIHVsb25nIGEgPSB4OwogICAgICAgIHVsb25nIGIgPSB5OwogICAgICAgIGIgPSBiIDw8IDMxOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgMzI7IGkrKykKICAgICAgICB7CiAgICAgICAgICAgIGlmIChhID49IGIpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGEgLT0gYjsKICAgICAgICAgICAgfQogICAgICAgICAgICBiID0gYiA+PiAxOwogICAgICAgIH0KICAgICAgICByZXR1cm4gKHVpbnQpYTsKICAgIH0KfQ==