Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [p-1 for p in P]
#print(P)

visited = set()
ans = 0
for i in range(N):
  if i in visited:
    continue
  tmp = []
  j = i
  while j not in visited:
    tmp.append(C[j])
    visited.add(j)
    j = P[j]
  #print(tmp,visited)  
  M = len(tmp)
  L = max(0,sum(tmp))
  now = L * (K // M)
  k = K % M
  tmp2 = 0
  tmp4 = 0
  for l in range(1,min(M,K)+1):
    tmp2 += tmp[l-1]
    tmp3 = tmp2
    for j in range(M):
      tmp4 = max(tmp4, tmp3) 
      tmp3 += tmp[(j+l)%M] - tmp[j%M]
      #print(tmp4, l, j)
      ans = max(ans, now+tmp4 if l <= k else now+tmp4-L)
  #ans = max(ans, now+tmp4 if l <= k else now+tmp4-L) 
  #print(i, L, now, l, k, tmp4, M, visited, now+tmp4)
  del tmp

flag = True
for c in C:
  if c > 0:
    flag = False
    
print(max(C) if flag else ans)

    
  
    


### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [p-1 for p in P]
#print(P)

visited = set()
ans = 0
for i in range(N):
  if i in visited:
    continue
  tmp = []
  j = i
  while j not in visited:
    tmp.append(C[j])
    visited.add(j)
    j = P[j]
  #print(tmp,visited)  
  M = len(tmp)
  L = max(0,sum(tmp))
  now = L * (K // M)
  k = K % M
  tmp2 = 0
  tmp4 = 0
  for l in range(1,min(M,K)+1):
    tmp2 += tmp[l-1]
    tmp3 = tmp2
    for j in range(M):
      tmp4 = max(tmp4, tmp3) 
      tmp3 += tmp[(j+l)%M] - tmp[j%M]
      #print(tmp4, l, j)
      ans = max(ans, now+tmp4 if l <= k else now+tmp4-L)
  #ans = max(ans, now+tmp4 if l <= k else now+tmp4-L) 
  #print(i, L, now, l, k, tmp4, M, visited, now+tmp4)
  del tmp

flag = True
for c in C:
  if c > 0:
    flag = False
    
print(max(C) if flag else ans)
### BUGGY CODE ###

mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

    N = int(input())
    A = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    dp = [[A[0]]]
    ID = [0] * (N+1)
    ans = [0] * (N+1)
    ans[1] = 1
    while que:
        v = que.popleft()
        flg = 1
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)
                if flg:
                    uu = u
                    flg = 0
                    continue
                a = A[u-1]
                ID[u] = len(dp)
                dp.append(dp[ID[v]][:])
                j = bisect_left(dp[-1], a)
                if j == len(dp[-1]):
                    dp[-1].append(a)
                    ans[u] = len(dp[-1])
                else:
                    dp[-1][j] = a
                    ans[u] = len(dp[-1])
        if flg == 0:
            a = A[uu-1]
            ID[uu] = ID[v]
            j = bisect_left(dp[ID[uu]], a)
            if j == len(dp[ID[uu]]):
                dp[ID[uu]].append(a)
            else:
                dp[ID[uu]][j] = a
            ans[uu] = len(dp[ID[uu]])

    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

    N = int(input())
    A = list(map(int, input().split()))
    adj = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    que = deque()
    que.append(1)
    seen = [0] * (N+1)
    seen[1] = 1
    ans = [0] * (N+1)
    ans[1] = 1
    LIS = []
    change = [[] for _ in range(N+1)]
    while que:
        v = que.pop()
        if v > 0:
            que.append(-v)
            a = A[v-1]
            if not LIS:
                LIS.append(a)
                change[v] = (0, -1)
            else:
                j = bisect_left(LIS, a)
                if j == len(LIS):
                    LIS.append(a)
                    ans[v] = len(LIS)
                    change[v] = (len(LIS) - 1, -1)
                else:
                    change[v] = (j, LIS[j])
                    LIS[j] = a
                    ans[v] = len(LIS)
            for u in adj[v]:
                if seen[u] == 0:
                    seen[u] = 1
                    que.append(u)
        else:
            v = -v
            i, x = change[v]
            if x == -1:
                LIS.pop()
            else:
                LIS[i] = x
    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from bisect import bisect_left
from sys import stdin



def main():
  ## input
  N,Q = map(int, stdin.readline().rstrip().split())
  STX = [[0,0,0] for _ in range(N)]
  for i in range(N):
    s,t,x = map(int, stdin.readline().rstrip().split())
    STX[i] = [x,s-x,t-x]
  Dn = [int(stdin.readline().rstrip()) for _ in range(Q)] + [10**10]
  ans = {}

  for x,s,t in sorted(STX):
    l = bisect_left(Dn,s)
    r = bisect_left(Dn,t)
    for i in range(r-l+1):
      if Dn[l] < t:
        ans[Dn[l]] = x
        Dn.pop(l)

  for d in Dn[:-1]:
    ans[d] = -1

  return ans


if __name__ == "__main__":
  ans = main()
  for d in sorted(list(ans.keys())):
    print(ans[d])
    


### FIXED CODE ###

import sys
from bisect import bisect_left



N,Q = map(int, input().split())
lines = sys.stdin.readlines()
kkk = []
for line in lines[:N]:
  s, t, x = map(int, line.split())
  kkk.append((x, s, t))
kkk.sort()
ddd = list(map(int, lines[N:]))

ans = [-1] * Q
skip = [-1] * Q
for x, s, t in kkk:
  ss = bisect_left(ddd, s - x)
  tt = bisect_left(ddd, t - x)
  while ss < tt:
    sk = skip[ss]
    if sk == -1:
      ans[ss] = x
      skip[ss] = tt
      ss += 1
    else:
      ss = sk

print('\n'.join(map(str, ans)))
### BUGGY CODE ###

N, M = map(int, input().split())
LRs = None
for i in range(M):
	l, r = map(int, input().split())
	if(LRs is None):
		LRs = set(range(l, r+1))
	else:
		LRs = LRs.intersection(set(range(l, r+1)))
print(str(len(LRs)))

### FIXED CODE ###

N, M = map(int, input().split())
l_max = 0
r_min = 10**5+1
for i in range(M):
	l, r = map(int, input().split())
	l_max = max(l, l_max)
	r_min = min(r, r_min)
if(l_max <= r_min):
	print(str(r_min - l_max + 1))
else:
	print("0")
### BUGGY CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
result = [A.count(i+1) for i in range(N)]

for r in result:
    print(r)


### FIXED CODE ###

N = int(input())
A = sorted(list(map(int, input().split())))
least = 1
result = [0] * N
for a in A:
    result[a-1] += 1
    if a != least:
        least = a

for r in result:
    print(r)
### BUGGY CODE ###

n = int(input())
i = 1
while True:
    if (i%2==0)and(i%n==0):
        print(i)
        break
    i += 1

### FIXED CODE ###

n = int(input())
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
print(lcm(2, n))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

def recursion_j(n, dp, i, j, k):
    if dp[i][j][k] > 0:
        return dp[i][j][k]
    if i == j == k == 0:
        return 0

    res = 0
    if i > 0:
        res += recursion_j(n, dp, i - 1, j, k) * i
    if j > 0:
        res += recursion_j(n, dp, i + 1, j - 1, k) * j
    if k > 0:
        res += recursion_j(n, dp, i, j + 1, k - 1) * k
    res += n
    res *= 1 / (i + j + k)
    dp[i][j][k] = res
    return res


def p_j():
    n = int(input())
    *a, = map(int, input().split())
    c = [0] * 3
    for a_ in a:
        c[a_ - 1] += 1
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    print(recursion_j(n, dp, c[0], c[1], c[2]))

p_j()

### FIXED CODE ###

def p_j_dp():
    n = int(input())
    *a, = map(int, input().split())
    c1 = a.count(1)
    c2 = a.count(2)
    c3 = a.count(3)
    dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    for k in range(c3 + 1):
        for j in range(c3 + c2 + 1 - k):
            for i in range(n + 1 - k - j):
                if i + j + k == 0:
                    continue
                res = n
                if i > 0:
                    res += i * dp[i - 1][j][k]
                if j > 0:
                    res += j * dp[i + 1][j - 1][k]
                if k > 0:
                    res += k * dp[i][j + 1][k - 1]
                res /= i + j + k
                dp[i][j][k] = res
    print(dp[c1][c2][c3])
    
p_j_dp()
### BUGGY CODE ###

from collections import deque
n = int(input())
l = [0 for i in range(n)]
l2 = []
l3 = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l2.append([a,b])
    l3[a].append(b)
    l3[b].append(a)
    l[a-1] += 1
    l[b-1] += 1
a = max(l)
print(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([1,0])
rl[1] = 1
cl = [[0 for i in range(n+1)] for i in range(n+1)]
while len(d):
    now,c = d.popleft()
    rl[now] = 1
    if c == 0:
        count = 1
        for i in l3[now]:
            cl[now][i] = count
            d.append([i,count])
            count += 1
    else:
        count = 1
        for i in l3[now]:
            if rl[i] == 0:
                if c == count:
                    count += 1
                cl[now][i] = count
                d.append([i,count])
                count += 1
for i in range(n-1):
    print(cl[l2[i][0]][l2[i][1]])

### FIXED CODE ###

from collections import deque
n = int(input())
l = [0 for i in range(n)]
l2 = []
l3 = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int,input().split())
    l2.append([a,b])
    l3[a].append(b)
    l3[b].append(a)
    l[a-1] += 1
    l[b-1] += 1
a = max(l)
print(a)
rl = [0 for i in range(n+1)]
d = deque()
d.append([1,0])
rl[1] = 1
dic = {}
while len(d):
    now,c = d.popleft()
    rl[now] = 1
    if c == 0:
        count = 1
        for i in l3[now]:
            dic["{0},{1}".format(now,i)] = count
            d.append([i,count])
            count += 1
    else:
        count = 1
        for i in l3[now]:
            if rl[i] == 0:
                if c == count:
                    count += 1
                dic["{0},{1}".format(now,i)] = count
                d.append([i,count])
                count += 1
for i in range(n-1):
    print(dic["{0},{1}".format(l2[i][0],l2[i][1])])
### BUGGY CODE ###

# import sys
# input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        if visited[i]==0:
            for j in range(len(tree[i])):
                node_tmp = tree[i][j]
                if visited[node_tmp-1]==1:
                    c[i] += c[node_tmp-1]
                    visited[i] = 1
print(" ".join(map(str,c)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))
### BUGGY CODE ###

from fractions import Fraction
from decimal import Decimal

n=int(input())
a=[Fraction(Decimal(input())) for _ in range(n)]

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*20 for _ in range(45)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for c2,c5 in pair:
    for cc2 in range(18-c2,45):
        for cc5 in range(18-c5,20):
            ans+=cnt[cc2][cc5]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)

### FIXED CODE ###

from fractions import Fraction
from decimal import Decimal

n=int(input())
a=[Fraction(Decimal(input())) for _ in range(n)]

num=[aa.numerator*10**9//aa.denominator for aa in a]

cnt=[[0]*50 for _ in range(50)]
pair=[]

for nu in num:
    c2=0
    c5=0
    while nu>0 and nu%2==0:
        nu//=2
        c2+=1
    
    while nu>0 and nu%5==0:
        nu//=5
        c5+=1
    
    cnt[c2][c5]+=1
    pair.append((c2,c5))
ans=0

for i in range(49,-1,-1):
    for j in range(49,-1,-1):
        if i+1<49:
            cnt[i][j]+=cnt[i+1][j]
        if j+1<49:
            cnt[i][j]+=cnt[i][j+1]

        if i+1<49 and j+1<49:
            cnt[i][j]-=cnt[i+1][j+1]

for c2,c5 in pair:
    ans+=cnt[max(0,18-c2)][max(0,18-c5)]
    if c2>=9 and c5>=9:
        ans-=1

print(ans//2)
### BUGGY CODE ###

n = int(input())
s = [0] * n
for i in range(n):
    s[i] = input()
s = sorted(s)
s = sorted([''.join(sorted(list(t))) for t in s])
count = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if s[j] > s[i]:
            break
        elif s[j] == s[i]:
            count += 1
print(count)


### FIXED CODE ###

from math import factorial

def unique(w):
    d = {}
    for c in w:
        if c in d.keys():
            d[c] += 1
        else:
            d.setdefault(c, 1)
    return list(d.values())

n = int(input())
s = [0] * n
for i in range(n):
    s[i] = input()
# s = sorted([''.join(sorted(list(t))) for t in s])
s = [''.join(sorted(list(t))) for t in s]
values = unique(s)
count = 0
for i in values:
    if i > 1:
        count += factorial(i) // factorial(2) // factorial(i - 2)
print(count)
### BUGGY CODE ###

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    n, m = LI()
    a = LI()
    b = [0 for _ in range(m)]
    c = [0 for _ in range(m)]

    for i in range(m):
        b[i], c[i] = LI()

    dic = collections.Counter(a)
    queue = collections.deque(sorted(list(set(a)|set(c))))

    mn = min(a)
    while queue[0] < mn:
        queue.popleft()

    for i in range(m):
        for x in list(queue):
            if x < c[i]:
                tem = dic[x]
                dic[x] = max(dic[x]-b[i], 0)
                b[i] -= tem-dic[x]
                dic[c[i]] += tem-dic[x]
                if dic[x] == 0:
                    queue.popleft()
                if b[i] == 0:
                    break
            else:
                break

    ans = 0
    for k, v in dic.items():
        ans += k*v

    print(ans)

        


main()


### FIXED CODE ###

import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():

    n, m = LI()
    a = LI()
    b = [0 for _ in range(m)]
    c = [0 for _ in range(m)]

    for i in range(m):
        b[i], c[i] = LI()

    dic = collections.Counter(a)
    queue = collections.deque(sorted(list(set(a)|set(c))))

    mn = min(a)
    while queue[0] < mn:
        queue.popleft()

    for i in range(m):
        cnt = 0
        for x in queue:
            if x < c[i]:
                tem = dic[x]
                dic[x] = max(dic[x]-b[i], 0)
                b[i] -= tem-dic[x]
                dic[c[i]] += tem-dic[x]
                if dic[x] == 0:
                    cnt += 1
                if b[i] == 0:
                    break
            else:
                break
        for _ in range(cnt):
            queue.popleft()
    ans = 0
    for k, v in dic.items():
        ans += k*v

    print(ans)

        


main()
### BUGGY CODE ###

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    children[a].append(b)

Ps = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    Ps[p] += x

Co = [0] * (N + 1)


def chase(now, nodes, su):
    Co[now] = Ps[now] + su
    nodes.append(now)
    for c in children[now]:
        chase(c, nodes, Co[now])


chase(1, [], 0)

Co.pop(0)
print(" ".join(map(str, Co)))

### FIXED CODE ###

import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline

N, Q = map(int, input().split())
children = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    children[a].append(b)

Ps = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    Ps[p] += x

Co = [0] * (N + 1)
import collections

q = collections.deque([(1, 0)])
while (len(q) > 0):
    now, pa = q.popleft()
    Co[now] = Ps[now] + Co[pa]
    for c in children[now]:
        q.append((c, now))

Co.pop(0)
print(" ".join(map(str, Co)))
### BUGGY CODE ###

k,s=list(map(int,input().split()))
o=0
for i in range(k+1):
    for u in range(k+1):
        for y in range(k+1):
            if (i+u+y)==s:
                o+=1
print(o)

### FIXED CODE ###

k,s=list(map(int,input().split()))
o=0
for i in range(k+1):
    for u in range(k+1):
        if 0<=(s-i-u)<=k:
            o+=1
print(o)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

def lcd(x0, y0):
    lx, ly = len(x0), len(y0)
    memo = [[None] * ly for _ in range(lx)]

    def memoize(x, y):
        if x < 0 or y < 0:
            return 0
        if memo[x][y] is not None:
            return memo[x][y]
        result = memo[x][y] = main(x, y)
        return result

    def main(x, y):
        return memoize(x - 1, y - 1) + 1 if x0[x] == y0[y] else max(memoize(x - 1, y), memoize(x, y - 1))

    return main(lx - 1, ly - 1)


n = int(input())
while n:
    print(lcd(input(), input()))
    n -= 1

### FIXED CODE ###

n = int(input())
for _ in range(n):
    a, b = input(), input()
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])

for x in s:
    g.add_edge(x[0],x[1])
di=nx.dijkstra_predecessor_and_distance(g,source=1)

if len(di[0])!=n:
    print("No")
    exit()

print("Yes")
for x in range(2,n+1):
    print(di[0][x][0])

### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
s=[list(map(int,input().split())) for i in range(m)]

g=nx.Graph()
g.add_nodes_from([i for i in range(1,n+1)])

for x in s:
    g.add_edge(x[0],x[1])
di=nx.predecessor(g,source=1)

if len(di)!=n:
    print("No")
    exit()

print("Yes")
for x in range(2,n+1):
    print(di[x][0])
### BUGGY CODE ###

from bisect import*
def main():
    root=[[],[]]
    def search_higher(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect(ptr[0],key)
            if i!=len(ptr[0]):ret=ptr[0][i]
            ptr=ptr[1][i]
        i=bisect(ptr[0],key)
        if i!=len(ptr[0]):ret=ptr[0][i]
        return ret
    def search_lower(key):
        ptr=root
        ret=None
        while ptr[1]:
            i=bisect_left(ptr[0],key)
            if i!=0:ret=ptr[0][i-1]
            ptr=ptr[1][i]
        i=bisect_left(ptr[0],key)
        if i!=0:ret=ptr[0][i-1]
        return ret
    def insert_rec(ptr,key):
        b_size=600
        if not ptr[1]:
            insort(ptr[0],key)
            if len(ptr[0])==b_size*2-1:
                ret=[ptr[0][:b_size],[]]
                ptr[0]=ptr[0][b_size:]
                return ret
        else:
            i=bisect(ptr[0],key)
            tmp=insert_rec(ptr[1][i],key)
            if tmp:
                ptr[0].insert(i,tmp[0].pop())
                ptr[1].insert(i,tmp)
                if len(ptr[1])==b_size*2:
                    ret=[ptr[0][:b_size],ptr[1][:b_size]]
                    ptr[0],ptr[1]=ptr[0][b_size:],ptr[1][b_size:]
                    return ret
    def insert(key):
        tmp=insert_rec(root,key)
        if tmp:root[0],root[1]=[tmp[0].pop()],[tmp,root]
    n,*a=map(int,open(0).read().split())
    l=[0]*n
    for i,v in enumerate(a,1):l[v-1]=i
    insert(0)
    insert(n+1)
    c=0
    for i,v in enumerate(l,1):
        c+=(search_higher(v)-v)*(v-search_lower(v))*i
        insert(v)
    print(c)
main()

### FIXED CODE ###

root=lambda x:x if par[x]==x else root(par[x])
same=lambda x,y:root(x)==root(y)
def unite(*z):
  x,y=map(root,z)
  if x!=y:
    if rank[x]<rank[y]:
      par[x]=y
      size[y]+=size[x]
    else:
      par[y]=x
      size[x]+=size[y]
      if rank[x]==rank[y]:rank[x]+=1
n,*a=map(int,open(0).read().split())
*par,=range(n)
rank=[1]*n
size=[1]*n
b=[0]*n
for i,t in enumerate(a):b[t-1]=i
c=0
for k in b[::-1]:
  l=r=1
  if k>0 and a[k-1]>a[k]:
    l+=size[root(k-1)]
    unite(k-1,k)
  if k+1<n and a[k+1]>a[k]:
    r+=size[root(k+1)]
    unite(k+1,k)
  c+=l*r*a[k]
print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

S = input()
T = input()
LS = len(S); LT = len(T)

memo = [[-1]*LT for i in range(LS)]
nxt = [[(0, None, None)]*(LT+1) for i in range(LS+1)]
def dfs(i, j):
    if i == LS or j == LT:
        return 0
    if memo[i][j] != -1:
        return memo[i][j]
    r0 = dfs(i+1, j); r1 = dfs(i, j+1)
    r = max(r0, r1)
    x = (0, i, j+1) if r0 < r1 else (0, i+1, j)
    if S[i] == T[j]:
        r2 = dfs(i+1, j+1) + 1
        if r < r2:
            r = r2
            x = (1, i+1, j+1)
    memo[i][j] = r
    nxt[i][j] = x
    return r

dfs(0, 0)
i = j = 0
ans = []
while i is not None:
    m, i0, j = nxt[i][j]
    if m:
        ans.append(S[i])
    i = i0
print(*ans, sep='')

### FIXED CODE ###

*S, = map(ord, input())
*T, = map(ord, input())
LS = len(S); LT = len(T)

dp = [[-1]*(LT+1) for i in range(LS+1)]
for i in range(LS-1, -1, -1):
    for j in range(LT-1, -1, -1):
        if S[i] == T[j]:
            dp[i][j] = max(dp[i+1][j+1] + 1, dp[i+1][j], dp[i][j+1])
        else:
            dp[i][j] = max(dp[i+1][j], dp[i][j+1])
i = j = 0
ans = []
while i < LS and j < LT:
    if S[i] == T[j]:
        if dp[i][j] == dp[i+1][j+1] + 1:
            ans.append(S[i])
            i += 1; j += 1
        elif dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
    else:
        if dp[i][j] == dp[i+1][j]:
            i += 1
        else:
            j += 1
print(*map(chr, ans), sep='')