Harryxun/stf_run huggingface dataset:
import numpy as np

n, k = map(int, input().split())
lst = list(map(int, input().split()))

array = np.array(lst)
po_array = array[array>=0]
ne_array = np.sort(abs(array[array<0]))

if len(po_array) >= len(ne_array):
    long_array = po_array
    short_array = ne_array
else:
    long_array = ne_array
    short_array = po_array

if len(short_array) > k:
    min_len = k
else:
    min_len = len(short_array)
    
if min_len == 0:
    print(long_array[k-1])
else:
    min_dist = 10**10
    for i in range(min_len):
        if i == k-1:
            dist = short_array[i]
        else:
            dist = short_array[i]*2 + long_array[k-i-2]
        if min_dist > dist:
            min_dist = dist
    if len(long_array) >= k:
        if min_dist > long_array[k-1]:
            min_dist = long_array[k-1]
    print(min_dist)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
lst = list(map(int, input().split()))

array = np.array(lst)
po_array = array[array>=0]
ne_array = abs(array[array<0])
ne_array.sort()

if len(po_array) >= len(ne_array):
    long_array = po_array
    short_array = ne_array
else:
    long_array = ne_array
    short_array = po_array

if len(short_array) > k:
    min_len = k
else:
    min_len = len(short_array)
        
if min_len == 0:
    print(long_array[k-1])
else:
    min_dist = 10**10
    for i in range(min_len):
        dist = 10**10
        if i == k-1:
            dist = short_array[i]
        elif k-i-1 <= len(long_array): 
            dist = min(short_array[i]*2 + long_array[k-i-2], short_array[i] + long_array[k-i-2]*2)
        if min_dist > dist:
            min_dist = dist
    if len(long_array) >= k:
        if min_dist > long_array[k-1]:
            min_dist = long_array[k-1]
    print(min_dist)
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    mid = deque([])
    for K,L,R in KLR:
      x = L - R
      if x==0:
        mid.append([K-1,L,R,x])
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    flag = [False] * (N)
    ans = 0
    for klr in left:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
    for klr in mid:
      ans += klr[1]

    print(ans)
    
main()

### FIXED CODE ###

N = int(input())
X = input()

l = [0] * (2*10**5+1)
ans = [0] * (2*10**5+1)
for i in range(2*10**5+1):
  l[i] = bin(i).count('1')
  
for i in range(2*10**5+1):
  x = i
  y = 0
  while x!=0:
    y += 1
    x %= l[x]
    
  ans[i] = y
  
X_count = X.count('1')
plu = X_count + 1
mi = X_count - 1
plu_res = 0
mi_res = 0
X_int = int(X,2)

for i in range(N):
  if X[i]=='0':
    continue
  else:
    plu_res += pow(2,N-i-1,plu)
    plu_res %= plu
    if mi>0:
      mi_res += pow(2,N-i-1,mi)
      mi_res %= mi
      
for i in range(N):
  if X[i]=='0':
    x = (plu_res + pow(2,N-i-1,plu)) % plu
    print(1 + ans[x])
  else:
    if mi!=0:
      x = (mi_res - pow(2,N-i-1,mi)) % mi
      print(1 + ans[x])
    else:
      print(0)
n, k = map(int, input().split())
h = list(map(int,input().split()))
num = 0
for i in range(n):
  if h[i] >= k:
    m += 1
print(m)

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int,input().split()))
num = 0
for i in range(n):
  if h[i] >= k:
    num += 1
print(num)
n = int(input())

xyh = []

for i in range(n):
    xyh.append(list(map(int, input().split())))

isOk = False
i = 0
j = 0
constant = -1

for i in range(101):
    for j in range(101):

        constant = -1
        for xyhTemp in xyh:
            if xyhTemp[2] != 0:
                temp = xyhTemp[2] + abs(i - xyhTemp[0]) + abs(j - xyhTemp[1])

                if constant == -1:
                    constant = temp

                if constant != temp:
                    break
        else:

            for p in xyh:
                if p[2] == 0 and constant - abs(i - p[0]) - abs(j - p[1]) > 0:
                    break
            else:
                isOk = True
                break
        
    if isOk:
        break

print(i, j, constant)
        


### FIXED CODE ###

N, T = list(map(int, input().split()))

ans = 100000
for i in range(N):
    c, t = list(map(int, input().split()))
    if t <= T and c <= ans:
        ans = c

if ans == 100000:
    print("TLE")
else:
    print(ans)
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter, deque
from bisect import bisect_right

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A, 1):
        idxs[a] = i
    lowers = deque([0, N + 1])
    ans = 0
    for a, i in enumerate(idxs[1:], 1):
        j = bisect_right(lowers, i)
        l, r = lowers[j - 1], lowers[j]
        lowers.insert(j, i)
        ans += (i - l) * (r - i) * a

    return ans

print(main())

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import Counter

def main():
    N = II()
    A = LI()
    idxs = [0] * (N + 1)
    for i, a in enumerate(A):
        idxs[a] = i
    ll = list(range(N + 1))
    rr = list(range(N + 1))
    ans = 0
    for a in range(N, 0, -1):
        idx = idxs[a]
        l, r = ll[idx], rr[idx]
        ans += (idx - l + 1) * (r - idx + 1) * a
        ll[r + 1] = l
        rr[l - 1] = r

    return ans

print(main())
# -*- coding: utf-8 -*-
from scipy.misc import comb

n, k = map(int, input().split())

mod = int(10 ** 9 + 7)

for i in range(1, k + 1):
    if i > n - k + 1:
        print(0)
    else:
        print(comb(k - 1, i - 1) * comb(n - k + 1, i) % mod)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

n, m = map(int, input().split())
g = [[] for _ in range(3 * n)]
for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    # u0 -> v1
    g[3 * u].append(3 * v + 1)
    # u1 -> v2
    g[3 * u + 1].append(3 * v + 2)
    # u2 -> v0
    g[3 * u + 2].append(3 * v)

s, t = map(int, input().split())
s = 3 * (s - 1)
t = 3 * (t - 1)

depth = dict()
depth[s] = 0
q = deque([s])


while(len(q) != 0):
    v = q.popleft()
    for u in g[v]:
        if u not in depth:
            q.append(u)
            depth[u] = depth[v] + 1

print(depth[t] // 3 if t in depth else -1)
import math


def main() -> None:
    a, b = input().split()

    print(math.floor(a * (b*100) / 100))

    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def main() -> None:
    a, b = input().split()

    print((int(a)*int(b.replace('.', ''))) // 100)

    return


if __name__ == '__main__':
    main()
import random
import sys

sys.setrecursionlimit(100000)

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}

def dps(g_mem, edge, now):
    count = g_mem[now]
    if edge.get(now):
        for e in edge[now]:
            if g_reached[e] == 0:
                g_reached[e] = 1
                count += dps(g_mem, edge, e)
    return count


ans = []
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        ans.append(dps(g_mem, edge, now))

# print(ans)
print(max(ans))


### FIXED CODE ###

import random
import sys

n, m = map(int, input().split())
# n, m = 200000, 200000
group = {i: 0 for i in range(1, n+1)}
edge = {}
g_mem = {}
g_num = 0
g_con = set()

for i in range(m):
    a, b = map(int, input().split())
    # a, b = random.sample(range(1,n+1), 2)
    if group[a]==0 and group[b] == 0:
        g_num += 1
        group[a] = g_num
        group[b] = g_num
        g_mem[g_num] = 2
    elif group[a] == 0:
        group[a] = group[b]
        g_mem[group[b]] += 1
    elif group[b] == 0:
        group[b] = group[a]
        g_mem[group[a]] += 1
    elif group[a] != group[b]:
        if edge.get(group[a]):
            edge[group[a]].add(group[b])
        else:
            edge[group[a]] = {group[b]}
        if edge.get(group[b]):
            edge[group[b]].add(group[a])
        else:
            edge[group[b]] = {group[a]}

# print(g_mem)
# print(sum(g_mem.values()))
# print(edge)

g_reached = {i: 0 for i in range(1, g_num+1)}
ans = list(g_mem.values())
for now in range(1, g_num+1):
    if g_reached[now] == 0:
        g_reached[now] = 1
        if edge.get(now):
            count = g_mem[now]
            queue = set(edge[now])
            while len(queue) > 0:
                next_now = queue.pop()
                if g_reached[next_now] == 0:
                    g_reached[next_now] = 1
                    count += g_mem[next_now]
                    queue |= edge[next_now]
                queue -= {now}
                now = next_now
            ans.append(count)


# print(ans)
if len(ans) > 0:
    print(max(ans))
else:
    print(1)
input_list=list(input())

#A,B,C,K
a = int(list[3]) - int(list[0])
b = int(list[3]) - int(list[1])
c = int(list[3]) - int(list[2])

calc = 1 * a + 0 * b - 1 * c

print(calc)

### FIXED CODE ###

input_list=list(input().split(" "))
#2000000000 0 0 2000000000
#A,B,C,K
a = int(input_list[3]) - int(input_list[0])
b = int(input_list[3]) - int(input_list[1])- int(input_list[0])
c = int(input_list[3]) - int(input_list[2])- int(input_list[1])- int(input_list[0])
if a < 0:
    calc = int(input_list[3])
elif b <= 0 and a >=0:
  calc = int(input_list[0])
else:
  calc = int(input_list[0]) - b
print(calc)
import collections
s = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
dif = sorted(list(set(alphabet) - set(s)))
if len(dif):
    print(s + dif[0])
else:
    if alphabet[::-1] == s:
        print(-1)
    else:
        tmp = [s]
        for i in range(25):
            if s[i] == alphabet[i]:
                continue
            else:
                tmp.append(s[:i-1] + alphabet[i])
        tmp.sort()
        print(tmp[tmp.index(s)+1])

### FIXED CODE ###

s = input()+chr(ord("a")-1)
ans = -1
for i in range(len(s)):
    t = s[:~i]
    dif = set(map(chr,range(ord(s[~i])+1,123))) - set(t)
    if dif:
        ans = t + min(dif)
        break
print(ans)
a,b,k =map(int,input().split())
p=[]
for i in range(max(a,b)):
  if i>0:
    if a%i == 0 and b%i == 0:
      p +=[i]
print(p[-k+1])

### FIXED CODE ###

a,b,k =map(int,input().split())
p=[]
for i in range(max(a,b)+1):
  if i>0:
    if a%i == 0 and b%i == 0:
      p +=[i]
print(p[-k])
from math import gcd

n = int(input())
a = list(map(int, input().split()))
result = []

left = [0] * (n+1)
right = [0] * (n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for j in range(n-1, -1, -1):
    right[j] = gcd(right[j+1], a[j])
for i in range(n):
    result.append(gcd(left[i], right[i+1]))

print(max(result))


### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
result = []

left = [0] * (n+1)
right = [0] * (n+1)
for i in range(n):
    left[i+1] = gcd(left[i], a[i])
for j in range(n-1, -1, -1):
    right[j] = gcd(right[j+1], a[j])
for i in range(n):
    result.append(gcd(left[i], right[i+1]))

print(max(result))
n = int(input())
a = list(map(int,input().split()))

b = 10000000
for i in range(100):
    sum = 0
    for j in range(n):
        sum = sum + abs(a[j] - (i + n))

    if sum < b:
        c = i
        b = sum


print(c)




### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))


for i in range(len(a)):
    a[i] = a[i] -(i+1)

a.sort()

x=a[int(int(len(a))/2)]

ans = 0
for i in range(len(a)):
    ans =ans+ abs(a[i]-x)

print(ans)
n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

 
if d[0]==1:
    s[0]=0
else:
    s[0]=1
 
if d[1]==1:
    s[1]=0
else:
    s[1]= s[0]+1
 
 
for i in range(2,n):
    if d[i]==1:
        s[i]=0
    else:
        s[i]=(s[i-1]+s[i-2])%1000000007
 
print( s[n-1] % 1000000007)


### FIXED CODE ###

n,k=map(int,input().split())
d=[0]*n
s=[0]*n

if k !=0:
    for i in range(k):
        p=int(input())
        d[p-1]=1

if n==1:
    print(1)
    exit()

 
if d[0]==1:
    s[0]=0
else:
    s[0]=1
 
if d[1]==1:
    s[1]=0
else:
    s[1]= s[0]+1
 
 
for i in range(2,n):
    if d[i]==1:
        s[i]=0
    else:
        s[i]=(s[i-1]+s[i-2])%1000000007
 
print( s[n-1] % 1000000007)
a,b=map(int,input().split())

if a+b=15:
  print("+")
elseif a*b=15:
  print("*")
else:
  print("×")

### FIXED CODE ###

A, B = map(int, input().split())
if(A+B==15):
    print("+")
elif(A*B==15):
    print("*")
else:
    print("x")
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
#    N = 10
#    K = 1
#    A = [0]*10
#    A[0] = 1

    for i in range(K):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[i]+1<=N:
                dm[x + A[x] + 1]+=-1
#            print(dm)
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    for i in range(min(K,50)):
        dm = [0]*N
        for x in range(N):
            dm[max(x - A[x],0)]+=1
            if x+A[x]+1<N:
                dm[x+A[x]+1]+=-1
        for j in range(1,N):
            dm[j]=dm[j-1]+dm[j]
        A[:] = dm[:]
    print(*A)

if __name__ == '__main__':
    main()
n = int(input())
mod = 10**9+7
l1 = []
l2 = []
l3 = []
for i in range(n):
    a,b = map(int,input().split())
    s1 = -b/a
    s2 = a/b
    if s2 in l1:
        l3[l1.index(s2)] += 1
    else:
        l1.append(s2)
        l2.append(-1)
        l3.append(1)
        if s1 in l1:
            ind = l1.index(s1)
            l2[-1] = ind
            l2[ind] = len(l1)-1

done = set()
ans = 1
for i in range(len(l2)):
    if l2[i] < 0:
        ans *= 2
        ans %= mod
    else:
        if l2[i] in done:
            continue
        c1 = l3[i]
        c2 = l3[l2[i]]
        count = (pow(2,c1,mod)+pow(2,c2,mod)-1)%mod
        ans *= count
        ans %= mod
        done.add(i)
        done.add(l2[i])

print(ans-1)
            


### FIXED CODE ###

import math

n = int(input())
mod = 10**9+7
d = {}

zero = 0
for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        zero += 1
    else:
        g = math.gcd(a,b)
        a //= g
        b //= g
        if b < 0:
            a = -a
            b = -b
        if b == 0 and a == -1:
            a = 1
        if a > 0:
            if (a,b) in d:
                d[(a,b)][0] += 1
            else:
                d[(a,b)] = [1,0]
        else:
            if (b,-a) in d:
                d[(b,-a)][1] += 1
            else:
                d[(b,-a)] = [0,1]
ans = 1
for (a,b),(c,d) in d.items():
    count = (pow(2,c,mod)+pow(2,d,mod)-1)%mod
    ans *= count
    ans %= mod


print((ans+zero-1)%mod)
import math


def resolve():
    n = int(input())
    print(2 ** int(math.log2(n)))


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    n = int(input())
    ans = 0
    for i in range(2, n + 1, 2):
        c = 0
        while i % 2 == 0:
            i //= 2
            c += 1
        if c > ans:
            ans = c
    print(2 ** ans)


if __name__ == "__main__":
    resolve()
a, b = map(int, input().split())
if ((a * b % 2) == 0:
    print('Even')
else:
    print('Odd')

### FIXED CODE ###

import sys
N = int(input())
t, x, y = 0, 0, 0
for i in range(N):
    in_t, in_x, in_y = map(int, input().split())
    t = in_t - t
    x = abs(in_x - x)
    y = abs(in_y - y)
    if (t >= x + y) & ((t - (x + y)) % 2 == 0):
        continue
    print('No')
    sys.exit()
print('Yes')
a, b, c = map(int input().split())
num = a*100 + b*10 + c
if num % 4 == 0:
  print("YES)
else:
  @rint("NO")

### FIXED CODE ###

# スペース区切りの整数の入力
a, b, c = map(int, input().split())
num = a*100 + b*10 + c
if num % 4 == 0:
  print("YES")
else:
  print("NO")
while 1:print(*[int(b)*2**i for i,b in enumerate(bin(int(input()))[2:][::-1])if int(b)])


### FIXED CODE ###

import sys
for d in sys.stdin:print(*[w for w in[2**i for i in range(10)]if int(d)&w])
n = input()
array = []
for i in range(n):
	inst = raw_input().split()
	if inst[0] == "insert":
		array.insert(0,inst[1])
	if inst[0] == "delete":
		if inst[1] in array:
			array.remove(inst[1])
	if inst[0] == "deleteFirst":
		array.pop[0]
	if inst[0] == "deleteLast":
		array.pop([len(array)-1])
print " ".join(i for i in array)

### FIXED CODE ###

n = input()
array = []
base = 0
for i in xrange(n):
    inst = raw_input().split()
    if inst[0][0] == 'i':
        array.append(int(inst[1]))
    elif inst[0] == "delete":
        if int(inst[1]) in array:
            x = array[::-1].index(int(inst[1]))
            if x != -1 and int(inst[1]):
                del array[-x-1]
    elif inst[0][6] == 'F':
        array.pop()
    else:
        base += 1
print (" ".join(map(str,array[base:][::-1])))
x500 = int(input())
x100 = int(input())
x50 = int(input())
xxx = int(input())

i = 0
j = 0
k = 0

count = 0
for i in range(x500):
    if total(i, j, k) == xxx:
        count += 1
    for j in range(x100):
        if total(i, j, k) == xxx:
            count += 1
        for k in range(x50):
            if total(i, j, k) == xxx:
                count += 1
print(count)


def total(i, j, k):
    return 500 * i + 100 * j + 50 * k

### FIXED CODE ###

A, B, C, x = [int(input()) for i in range(4)]
print(sum(500 * a + 100 * b + 50 * c == x for a in range(A+1) for b in range(B+1) for c in range(C+1)))
d, t, s = map(int, input().split())
ans = d/s
print('Yes' if ans < float(t) else "No"

### FIXED CODE ###

d, t, s = map(int, input().split())
ans = d/s
print('Yes' if ans <= t else "No")
n=int(input())
m=int(input())
if(n==m):
    print("Yes\n")
else:
    print("No\n")

### FIXED CODE ###

from sys import stdin

def main():
    n,m = map(int,stdin.readline().split())
    if(n==m):
        print("Yes")
    else:
        print("No")

main()
s, t = map(input().split())
a, b = map(int, input().split())
u = input()

if s == u:
    print(a - 1, b)
else:
    print(a, b-1)


### FIXED CODE ###

s, t = input().split()
a, b = map(int, input().split())
u = input()

if s == u:
    print(a - 1, b)
else:
    print(a, b-1)
def fun():
	n = int(input()
	A = list(map(int,input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod*=a
		if(prod>1000000000000000000):
			print(-1)
			return
	print(prod)



fun()

### FIXED CODE ###

def fun():
	n = int(input())
	A = list(map(int,input().split()))
	if 0 in A:
		print(0)
		return
	prod = 1
	for a in A:
		prod*=a
		if(prod>1000000000000000000):
			print(-1)
			return
	print(prod)
 
 
 
fun()
N = int(input())
A = list(map(int, input().split()))
DP = [[-1 for _1 in range(10000)] for _ in range(N) ]

for i in range(1000//A[0]+1):
    DP[0][i] = 1000 - A[0]*i

max_stock = 1000//A[0]
for j in range(1, N):
    today = A[j]
    DP[j][0] = max(DP[j-1][0], DP[j-1][max_stock] + max_stock*today)
    max_stock = DP[j-1][0]//today
    DP[j][max_stock] =  DP[j-1][0] - max_stock*today




print(DP[N-1][0])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
money = 1000
for i in range(N-2):
    today, tomorrow = A[i], A[i+1]
    if today < tomorrow:
        money = (money//today)*tomorrow + money%today
if A[N-2]< A[N-1]:
    money = (money//A[N-2]) * A[N-1] + money%A[N-2]

print(money)
n = int(input())
hs = map(int, input.split())
count = 1
maxh = 0
for i in range(1,n):
  maxh = max(maxh, hs[i-1])
  if hs[i]>maxh:
    count += 1
 print(count)

### FIXED CODE ###

n = int(input())
hs = input().split()
count = 1
maxh = 0
for i in range(1,n):
    maxh = max(maxh, int(hs[i-1]))
    if int(hs[i])>=maxh:
        count += 1
print(count)
n,x,m=map(int,input().split())

if n<=m*3:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    for i in range(icnt):
        asum0+=ai0
        ai0=(ai0*ai0)%m
        icnt0+=1
        if ai0==ai:
            break
    icntk=icnt-icnt0
    n0=n-1-icnt0
    nk=n0//icntk
    nr=n0%icntk
    asumk=asum-asum0
    asumr=0
    air=ai
    for i in range(nr):
        asumr+=air
        air=(air*air)%m
    asumr+=air
       
    ans=asum0+asumk*nk+asumr    
    print(ans)       
        


### FIXED CODE ###


n,x,m=map(int,input().split())

if x==0:
    print(0)
elif x==1:
    print(n)
elif m==1:
    print(0)
elif n<=m*2:
    asum=x
    ai=x
    for i in range(1,n):
        ai=(ai*ai)%m
        asum+=ai
    print(asum)
    
else:
    aa=[]
    ai=x
    icnt=0
    asum=0
    while not ai in aa:
        asum+=ai
        aa.append(ai)
        ai=(ai*ai)%m
        icnt+=1
    asum0=0
    ai0=x
    icnt0=0
    if ai!=x:
        for i in range(icnt+1):
            asum0+=ai0
            ai0=(ai0*ai0)%m
            icnt0+=1
            if ai0==ai:
                break
    icntk=icnt-icnt0
    if icntk==0:
#        print("0:",ai,asum,icnt,ai0,asum0,icnt0)
        icntk=1
        n0=n-1
        nk=n0//icntk
        nr=0
        asumk=ai0
        asumr=0
        ans=asum0+x*(n-icnt0)
        print(ans)       
    else:
#        print("1:",ai,asum,icnt,ai0,asum0,icnt0)
        n0=n-1-icnt0
        nk=n0//icntk
        nr=n0%icntk
        asumk=asum-asum0
        asumr=0
        air=ai
        for i in range(nr):
            asumr+=air
            air=(air*air)%m
        asumr+=air
       
        ans=asum0+asumk*nk+asumr    
        print(ans)