static int Dominator(int[] a)
{
    var size = 0;
    var value = 0;
    var index = 0;

    for (int k = 0; k < a.Length; k++)
    {
        var v = a[k];
        if (size == 0)
        {
            size++;
            value = v;
            index = k;
        }
        else if (value != v)
        {
            size--;
        }
        else
        {
            size++;
        }
    }

    var candidate = size > 0 ? value : -1;
    var count = 0;
    foreach (var v in a)
    {
        if (v == candidate)
        {
            count++;
        }
    }

    if (count <= a.Length / 2.0)
    {
        index = -1;
    }

    return index;
}

static int EquiLeader(int[] a)
{
    var leaderSize = 0;
    var value = 0;

    foreach (var v in a)
    {
        if (leaderSize == 0)
        {
            leaderSize++;
            value = v;
        }
        else if (value != v)
        {
            leaderSize--;
        }
        else
        {
            leaderSize++;
        }
    }

    var candidate = leaderSize > 0 ? value : -1;
    var leaderCount = 0;
    foreach (var v in a)
    {
        if (v == candidate)
        {
            leaderCount++;
        }
    }

    var leader = -1;
    if (leaderCount > a.Length / 2.0)
    {
        leader = candidate;
    }

    var count = a.Length;
    var lLeaderCount = 0;
    var equiLeaders = 0;

    for (int k = 0; k < count; k++)
    {
        var v = a[k];
        var leftHalf = (k + 1) / 2;
        var rightHalf = (count - k - 1) / 2;
        if (v == leader)
        {
            lLeaderCount++;
        }

        var rLeaderCount = leaderCount - lLeaderCount;
        if (lLeaderCount > leftHalf && rLeaderCount > rightHalf)
        {
            equiLeaders++;
        }
    }

    return equiLeaders;
}

static int FibFrog(int[] a)
{
    var size = a.Length;

    var fib = new List<int> { 0, 1 };
    for (int i = 1; fib[i] <= size;)
    {
        i++;
        fib.Add(fib[i - 1] + fib[i - 2]);
    }

    var queue = new Queue<(int Idx, int Jmp)>();
    queue.Enqueue((-1, 0));

    var visited = new bool[size];

    while (queue.Count > 0)
    {
        var (idx0, jmp) = queue.Dequeue();
        for (int i = fib.Count - 1; i >= 2; i--)
        {
            var idx = idx0 + fib[i];
            if (idx == size)
            {
                return jmp + 1;
            }
            if (idx > size || visited[idx] || a[idx] == 0)
            {
                continue;
            }
            if (a[idx] == 1)
            {
                visited[idx] = true;
                queue.Enqueue((idx, jmp + 1));
            }
        }
    }

    return -1;
}

static int Fish(int[] a, int[] b)
{
    var size = a.Length;
    var dead = 0;
    var fish = new Stack<int>();

    for (int i = 0; i < size; i++)
    {
        if (b[i] == 1)
        {
            fish.Push(a[i]);
        }
        else
        {
            while (fish.Count > 0)
            {
                dead++;
                if (a[i] > fish.Peek())
                {
                    fish.Pop();
                }
                else
                {
                    break;
                }
            }
        }
    }

    return size - dead;
}

static int Flags(int[] a)
{
    var size = a.Length;
    if (size == 0)
    {
        return 0;
    }

    var peaks = new bool[size];
    var next = new int[size];

    for (int i = 1; i < size; i++)
    {
        var right = i + 1 < size ? a[i + 1] : 0;
        peaks[i] = a[i - 1] < a[i] && a[i] > right;
    }

    next[size - 1] = -1;
    for (int i = size - 2; i >= 0; i--)
    {
        next[i] = peaks[i] ? i : next[i + 1];
    }

    var result = 0;
    for (int i = 1; i * (i - 1) <= size; i++)
    {
        var pos = 0;
        var num = 0;
        while (pos < size && num < i)
        {
            pos = next[pos];
            if (pos == -1)
            {
                break;
            }
            num++;
            pos += i;
        }
        result = Math.Max(result, num);
    }

    return result;
}

static long FrogJmp(long x, long y, long d)
{
    return (long)Math.Ceiling((double)(y - x) / d);
}

static int FrogRiverOne(int x, int[] a)
{
    var existing = new HashSet<int>();

    for (int k = 0; k < a.Length; k++)
    {
        var i = a[k];
        if (i <= x && existing.Add(i) && existing.Count == x)
        {
            return k;
        }
    }

    return -1;
}

static int[] GenomicRangeQuery(string s, int[] p, int[] q)
{
    var r = new int[p.Length];

    for (int k = 0; k < p.Length; k++)
    {
        var pi = p[k];
        var length = q[k] - pi + 1;
        var subStr = s.Substring(pi, length);

        if (subStr.Contains('A'))
        {
            r[k] = 1;
        }
        else if (subStr.Contains('C'))
        {
            r[k] = 2;
        }
        else if (subStr.Contains('G'))
        {
            r[k] = 3;
        }
        else
        {
            r[k] = 4;
        }
    }

    return r;
}

static bool IsIPv4Address(string inputString)
{
    var parts = inputString.Split('.');

    foreach (var v in parts)
    {
        if (!long.TryParse(v, out var n) || n > 255 || v == "" || v != n.ToString())
        {
            return false;
        }
    }

    return parts.Length == 4;
}

static int[] Ladder(int[] a, int[] b)
{
    var size = a.Length;
    var r = new int[size];
    var mod = (1 << b.Max()) - 1;

    var limit = a.Max();
    var fib = new int[limit + 2];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < limit + 2; i++)
    {
        fib[i] = (fib[i - 1] + fib[i - 2]) & mod;
    }

    for (int i = 0; i < size; i++)
    {
        r[i] = fib[a[i] + 1] & ((1 << b[i]) - 1);
    }

    return r;
}