# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def fib(N):
    F = [0, 1]
    while F[-1] < N:
        F.append(F[-1] + F[-2])
    return F

def solution(A):
    # write your code in Python 3.6
    F = fib(len(A)+1)
    steps = [-1] * (len(A) + 1)
    for f in F[1:]:
        if f - 1 == len(A) or f - 1 < len(A) and A[f-1] == 1:
            steps[f-1] = 1
    if steps[-1] != -1:
        return steps[-1]
    for i in range(0, len(A)):
        if steps[i] != -1: 
            for f in F[2:]:
                if i + f > len(A): break
                if i + f == len(A) or A[i+f] == 1:
                    if steps[i+f] == -1:
                        steps[i+f] = steps[i] + 1
                    else:
                        steps[i+f] = min(steps[i+f], steps[i] + 1)
    return steps[-1]

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A, B):
    # write your code in Python 3.6
    n = max(A)
    F = [0] * (n + 1)
    F[0] = F[1] = 1
    for i in range(2, n + 1):
        F[i] = (F[i-1] + F[i-2]) % 2 ** 30
    Bi = [2**i for i in range(31)]
    return [F[A[i]]%Bi[B[i]] for i in range(len(A))]

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    return gcd(b, a % b)

def check(a, b):
    if a < b:
        a, b = b, a
    c = a
    while c != 1:
        div = gcd(c, b)
        if div == 1:
            return False
        c //= div
    c = b
    while c != 1:
        div = gcd(a, c)
        if div == 1:
            return False
        c //= div
    return True

def solution(A, B):
    # write your code in Python 3.6
    return sum(1 for i in range(len(A)) if check(A[i], B[i]))

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def gcd(a, b):
    if a % b == 0:
        return b
    return gcd(b, a % b)

def solution(N, M):
    # write your code in Python 3.6
    return N // gcd(N, M)

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(K, M, A):
    # write your code in Python 3.6
    counter = [0] * (M + 2)
    for a in A:
        counter[a] += 1
    for i in range(K):
        counter[A[i]+1] += 1
        counter[A[i]] -= 1
    nums = set()
    for s, c in enumerate(counter):
        if c > len(A) / 2:
            nums.add(s)
            break
    for i in range(1, len(A)-K+1):
        counter[A[i-1]+1] -= 1
        counter[A[i-1]] += 1
        counter[A[i+K-1]+1] += 1
        counter[A[i+K-1]] -= 1
        if counter[A[i-1]] > len(A) / 2:
            nums.add(A[i-1])
        if counter[A[i+K-1]+1] > len(A) / 2:
            nums.add(A[i+K-1]+1)
    return list(sorted(nums))

# This file is to convert keras model in tensorflow
from keras import backend as K
import tensorflow as tf

def freeze_session(session, keep_var_names=None, output_names=None, clear_devices=True):
    """
    Freezes the state of a session into a pruned computation graph.

    Creates a new computation graph where variable nodes are replaced by
    constants taking their current value in the session. The new graph will be
    pruned so subgraphs that are not necessary to compute the requested
    outputs are removed.
    @param session The TensorFlow session to be frozen.
    @param keep_var_names A list of variable names that should not be frozen,
                          or None to freeze all the variables in the graph.
    @param output_names Names of the relevant graph outputs.
    @param clear_devices Remove the device directives from the graph for better portability.
    @return The frozen graph definition.
    """
    from tensorflow.python.framework.graph_util import convert_variables_to_constants
    graph = session.graph
    with graph.as_default():
        freeze_var_names = list(set(v.op.name for v in tf.global_variables()).difference(keep_var_names or []))
        output_names = output_names or []
        output_names += [v.op.name for v in tf.global_variables()]
        # Graph -> GraphDef ProtoBuf
        input_graph_def = graph.as_graph_def()
        if clear_devices:
            for node in input_graph_def.node:
                node.device = ""
        frozen_graph = convert_variables_to_constants(session, input_graph_def,
                                                      output_names, freeze_var_names)
        return frozen_graph

from keras.models import load_model
model = load_model('./resnet10.hdf5')
print(model.outputs)
# [<tf.Tensor 'dense_2/Softmax:0' shape=(?, 10) dtype=float32>]
print(model.inputs)
# [<tf.Tensor 'conv2d_1_input:0' shape=(?, 28, 28, 1) dtype=float32>]

frozen_graph = freeze_session(K.get_session(),
                              output_names=[out.op.name for out in model.outputs])

# Save to ./model/tf_model.pb
tf.train.write_graph(frozen_graph, "model", "resnet10.pb", as_text=False)
print("model saved in pb file")

import keras
model = keras.models.load_model('./resnet10.hdf5')
print(model.outputs)
# [<tf.Tensor 'dense_2/Softmax:0' shape=(?, 10) dtype=float32>]
print(model.inputs)
# [<tf.Tensor 'conv2d_1_input:0' shape=(?, 28, 28, 1) dtype=float32>]

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def check(peaks, A, k):
    start, i = 0, -1
    while start < len(A):
        end = start + k
        while i < len(peaks) - 1:
            i += 1
            if start <= peaks[i] < end:
                break
        else:
            return False
        start += k
    return True

def solution(A):
    # write your code in Python 3.6
    if len(A) < 3:
        return 0
    peaks = []
    for i in range(len(A)-2):
        if A[i] < A[i+1] and A[i+1] > A[i+2]:
            peaks.append(i+1)
    if len(peaks) == 0:
        return 0
    for i in range(len(peaks), 0, -1):
        if len(A) % i == 0 and check(peaks, A, len(A)//i):
            return i

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(A):
    # write your code in Python 3.6
    num, leader = 1, A[0]
    for a in A[1:]:
        if a == leader:
            num += 1
        elif num > 0:
            num -= 1
        else:
            num = 1
            leader = a
    num = A.count(leader)
    if num <= len(A) / 2:
        return 0
    curNum = 0
    Sum = 0
    for i, a in enumerate(A):
        if a == leader:
            curNum += 1
        if curNum > (i+1) / 2 and num - curNum > (len(A)-i-1) / 2:
            Sum += 1
    return Sum

def paginator(page, pagination):
    try:
        rend = """
            <ul class="pagination">
              {% if page > 1 %}
                <li><a href="?page={{ page - 1 }}"><i class="fa fa-chevron-left"></i></a></li>
              {% endif %}
        
              {% for p in range(pagination.get_page_count()) %}
                <li><a href="?page={{ p + 1 }}">{{ p + 1 }}</a></li>
              {% endfor %}
        
              {% if page < pagination.get_page_count() %}
                <li><a href="?page={{ page + 1 }}"><i class="fa fa-chevron-right"></i></a></li>
              {% endif %}
            </ul>
        """
        return render_template_string(rend, page=page, pagination=pagination)
    except:
        return 'error paginator() {}'.format(str(sys.exc_info()))