Problem:


Score : 400 points

Problem Statement

One day, Snuke was given a permutation of length N, a_1, a_2, ..., a_N, from his friend.

Find the following:

Constraints

1 ≦ N ≦ 200,000

(a_1, a_2, ..., a_N) is a permutation of (1, 2, ..., N).

Input

The input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

9

Sample Input 2

4
1 3 2 4

Sample Output 2

19

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

85



Sample input:
3
2 1 3


Sample output:
9

Submission status: Time Limit Exceeded

Solution code:
def bin_search(queue, num):
    if len(queue) == 0:
        return 0
    l = 0
    r = len(queue)
    while r-l > 1:
        m = (l+r) // 2
        if queue[m] < num:
            l = m
        else:
            r = m
            
    if l == 0 and queue[0] > num:
        r = 0
    return r


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

yyy = 0
for i in range(n):
    a[i] -= 1
    if i > 0 and a[i] > a[i-1]:
        yyy += 1
        
if yyy > n/2:
    b = []
    for i in range(n):
        b.append(a[n-1-i])
    a = b
        

loc = [-1 for i in range(n)]
for i in range(n):
    loc[a[i]] = i

l = [-1 for i in range(n)]
r = [-1 for i in range(n)]

q = []

for i in range(n):
    ind = bin_search(q, a[i])
    for j in range(ind, len(q)):
        r[q[j]] = i
    if ind ==len(q):
        q.append(a[i])
    else:
        q[ind] = a[i]
    q = q[:ind+1]
    if ind==0:
        l[a[i]] = 0
    else:
        l[a[i]] = loc[q[ind-1]]+1

for i in range(len(q)):
    r[q[i]] = n
    
ans = 0    
for i in range(n):
    a = (i+1) * (loc[i]-l[i]+1) * (r[i]-loc[i])
    ans += a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bin_search(queue, num):
    if len(queue) == 0:
        return 0
    l = 0
    r = len(queue)
    while r-l > 1:
        m = (l+r) // 2
        if queue[m] < num:
            l = m
        else:
            r = m
            
    if l == 0 and queue[0] > num:
        r = 0
    return r


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

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

loc = [-1 for i in range(n)]
for i in range(n):
    loc[a[i]] = i

l = [-1 for i in range(n)]
r = [-1 for i in range(n)]

q = []

for i in range(n):
    ind = bin_search(q, a[i])
    for j in range(ind, len(q)):
        r[q[j]] = i
    if ind ==len(q):
        q.append(a[i])
    else:
        q[ind] = a[i]
    q = q[:ind+1]
    if ind==0:
        l[a[i]] = 0
    else:
        l[a[i]] = loc[q[ind-1]]+1

for i in range(len(q)):
    r[q[i]] = n
    
ans = 0    
for i in range(n):
    a = (i+1) * (loc[i]-l[i]+1) * (r[i]-loc[i])
    ans += a

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    import numpy as np
    A = np.array(A)

    q = [A]
    ans = 0
    while q:
        A = q.pop()
        i = np.argmin(A)
        if A[:i].size != 0:
            q.append(A[:i])
        if A[i+1:].size != 0:
            q.append(A[i+1:])
        ans += A[i]*(i+1)*(A.size-i)

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    import numpy as np
    A = np.array(A)

    q = [A]
    ans = 0
    while q:
        A = q.pop()
        i = np.argmin(A)
        if len(A[:i]):
            q.append(A[:i])
        if len(A[i+1:]):
            q.append(A[i+1:])
        ans += A[i]*(i+1)*(len(A)-i)

    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):
    def f(A):
        n = len(A)
        if not n:
            return 0
        if n == 1:
            return A[0]

        i = A.index(min(A))
        return A[i]*(i+1)*(n-i) + f(A[:i]) + f(A[i+1:])

    return f(A)


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()
dd = defaultdict(int)

for i,a in enumerate(aa):
	dd[a] = i+1


li = [0,N+1]
ans = 0
for a in range(1,N+1):
	i = dd[a]
	ind = bisect.bisect_left(li,i)
	ans += (i-li[ind-1])*(li[ind]-i)*a
	li.insert(ind,i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Treap():
    class Node():
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data
            self.priority = random.random()
            # print(data, self.priority)

        def to_dict(self):
            d = {
                'data': self.data,
            }

            if self.left:
                d['left'] = self.left.to_dict()
            if self.right:
                d['right'] = self.right.to_dict()

            return d

        def __str__(self):
            return json.dumps(self.to_dict(), indent='  ')

    def __init__(self):
        self.__root = None

    def __insert(self, node, data):
        if node is None:
            return self.Node(data)
        if data < node.data:
            node.left = self.__insert(node.left, data)
            if node.priority < node.left.priority:
                node = self.__rotate_right(node)
        else:
            node.right = self.__insert(node.right, data)
            if node.priority < node.right.priority:
                node = self.__rotate_left(node)

        return node

    def __rotate_left(self, node):
        tmp_node = node.right
        node.right = tmp_node.left
        tmp_node.left = node
        return tmp_node

    def __rotate_right(self, node):
        tmp_node = node.left
        node.left = tmp_node.right
        tmp_node.right = node
        return tmp_node

    def insert(self, data):
        self.__root = self.__insert(self.__root, data)
        return self

    def __find_lcr(self, data, node, lv, rv):
        if node is None:
            return lv, None, rv
        if data == node.data:
            return lv, data, rv
        if lv < node.data < data:
            lv = node.data
        if data < node.data < rv:
            rv = node.data
        if data < node.data:
            return self.__find_lcr(data, node.left, lv, rv)
        else:
            return self.__find_lcr(data, node.right, lv, rv)

    def find_lcr(self, data):
        return self.__find_lcr(data, self.__root, -sys.maxsize, sys.maxsize)

    def __hight(self, node):
        if node is None:
            return 0
        lh = 1
        if node.left:
            lh += self.__hight(node.left)

        rh = 1
        if node.right:
            rh += self.__hight(node.right)
        return max(lh, rh)

    @property
    def hight(self):
        return self.__hight(self.__root)


@mt
def slv(N, A):
    ans = 0
    a2i = [0] * (N+1)
    for i, a in enumerate(A):
        a2i[A[i]] = i

    vi = Treap()
    vi.insert(-1)
    vi.insert(N)

    for a in range(1, N+1):
        i = a2i[a]
        l, _, r = vi.find_lcr(i)
        l += 1
        ans += (i - l + 1) * (r - i) * a
        vi.insert(i)
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))

    # A = list(range(1, 200000+1))
    # for _ in range(100):
    #     random.shuffle(A)
    #     N = len(A)
    #     print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A):

    # st = SegmentTree(N)
    # for i, d in enumerate(A):
    #     st.update(i, d)

    # ans = 0
    # for i in range(N):
    #     # print(i)
    #     for j in range(i, N):
    #         # print(i, j)
    #         # ans += min(A[i:j+1])
    #         ans += st.query(i, j+1)
    ans = 0
    a2i = [0] * (N+1)
    for i, a in enumerate(A):
        a2i[A[i]] = i

    vi = [-1, N]
    for a in range(1, N+1):
        i = a2i[a]
        j = bisect.bisect_right(vi, i)
        l = vi[j-1] + 1
        r = vi[j]

        ans += (i - l + 1) * (r - i) * a
        bisect.insort(vi, i)

    return ans


def main():
    N = read_int()
    A = read_int_n()

    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

n = int(input())
A = [int(i) for i in input().split()]

ans = 0

B = [(0, 0)]

for i, a in zip(range(1, n+1), A):
    B.append((a, i))

B.sort()

sortedlist = []
    
for i in range(1, n+1):
    j = bisect(sortedlist, B[i][1])
    left = B[i][1] - (sortedlist[j-1] if j-1 >= 0 else 0) - 1
    right = (sortedlist[j] - 1 if j < i-1 else n) - B[i][1]
    sortedlist.insert(j, B[i][1])

    ans += (left + 1) * (right + 1) * B[i][0]
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

p = dict((x, i + 1) for i, x in enumerate(A))

t = [0, N + 1]

import bisect

result = 0
for x in range(1, N+1):
    n = p[x]
    i = bisect.bisect_left(t, n)
    t.insert(i, n)
    result += x * (n - t[i-1]) * (t[i+1] - n)
    # print(n, i, t)

print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def cnt(n, p):
	ct = 0
	for i in range(1,n+1):
		for j in range(n-i+1):
			if p in range(j,j+i):
				ct+=1
	return ct

def sanc(ll):
	if len(ll) == 1:
		return ll[0]
	if len(ll) == 0:
		return 0
	p = np.argmin(ll)
	n = len(ll)
	cc = cnt(n,p)
	return sanc(ll[:p]) + cc*ll[p] + sanc(ll[p+1:])


n=int(input())
a=np.array([int(x) for x in input().split()])
print(int(sanc(a)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n=int(input())
a=np.array([int(x) for x in input().split()])
sm=0
for i in range(n):
	for j in range(i,n):
		sm+=np.min(a[i:j+1])

print(sm)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys, math, copy
# import fractions, itertools
# import numpy as np
# import scipy
# sys.setrecursionlimit(1000000)

HUGE = 2147483647
HUGEL = 9223372036854775807
ABC = "abcdefghijklmnopqrstuvwxyz"

def find_lr(an, i0):
    n = len(an)
    l = -1
    r = n
    for k in range(i0):
        if an[k] < an[i0]:
            l = k
    for k in reversed(range(i0 + 1, n)):
        if an[k] < an[i0]:
            r = k
    return l, r

def test_find_lr():
    an = [2, 1, 3]
    assert find_lr(an, 1) == (-1, 3)
    assert find_lr(an, 2) == (1, 3)
    assert find_lr(an, 0) == (-1, 1)

def main():
    n = int(input())
    an = list(map(int, input().split()))
    assert len(an) == n

    pos0 = [None for i in range(n)]
    res = 0
    for i in range(n):
        l, r = find_lr(an, i)
        res += (i - l) * (r - i) * an[i]

    print(res)

main()
# test_find_lr()

Submission status: Time Limit Exceeded

Solution code:
import bisect


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

    s = [0, N+1]
    order = [0]*(N+1)

    for i in range(N):
        order[a[i]] = i+1

    ans = 0
    for i in range(1, N+1):
        bisect.insort_left(s, order[i])
        ans += i*(order[i]-s[bisect.bisect_left(s, order[i])-1]) * \
            (s[bisect.bisect_left(s, order[i])+1]-order[i])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
a = list(map(int, input().split()))

s = [0, N+1]
order = [0]*(N+1)

for i in range(N):
    order[a[i]] = i+1

ans = 0
for i in range(1, N+1):
    bisect.insort_left(s, order[i])
    ans += i*(order[i]-s[bisect.bisect_left(s, order[i])-1]) * \
        (s[bisect.bisect_left(s, order[i])+1]-order[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = [int(i) for i in input().split()]
b = [0 for i in range(n)]
for i in range(n): b[a[i]-1] = i
ans,c = (b[0]+1)*(n-b[0]),[b[0]]
for i in range(1,n):
	x = bisect.bisect_left(c,b[i])
	if 0<x<len(c): ans += (c[x]-b[i])*(b[i]-c[x-1])*(i+1)
	elif x==0: ans += (c[0]-b[i])*(b[i]+1)*(i+1)
	elif x==len(c): ans += (b[i]-c[-1])*(n-b[i])*(i+1)
	bisect.insort_left(c,b[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(n):
	num,num2 = 1,1
	for j in range(i+1,n):
		if a[j]>a[i]: num+=1
		else: break
	for j2 in range(i-1,-1,-1):
		if a[j2]>a[i]: num2+=1
		else: break
	ans += a[i]*num*num2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
src = list(map(int,input().split()))
ans = 0
for i,a in enumerate(src):
     l = r = 0
     for j in range(i-1,-1,-1):
         if src[j] < a: break
         l += 1
     for j in range(i+1,N):
         if src[j] < a: break
         r += 1
     ans += (l+1)*(r+1)*a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
t=tuple(map(int,input().split()))
sum=0
for i in range(1,N+1):
    for _ in range(i,N+1):
        sum+=min(t[(i-1):(_)])
print(sum)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
ls = map(int, raw_input().split())
s = 0
for i,v in enumerate(ls):
    l = i-1
    while l >= 0 and v < ls[l]:
        l -= 1
    r = i+1
    while r < n and v < ls[r]:
        r += 1
    s += v * (i-l) * (r-i)
print s

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
l = map(int, raw_input().split())
ln = []
ret = sum(l)
while len(l) > 1:
    for i in range(1,len(l)):
        ln.append(min(l[i],l[i-1]))
    ret += sum(ln)
    l = ln
    ln = []
print ret

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding:utf-8 -*-

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

data = [float('inf')] * (2 * N - 1)

def update(i, val):
    i += N-1
    data[i] = val
    while i > 0:
        i = (i - 1) // 2
        data[i] = min(data[2*i+1], data[i*2+2])

for i in range(N):
    update(i, a[i])

def query(a, b, k, l, r):
    if l <= a and b <= r:
        return data[k]
    elif b <= l or r <= a:
        return float('inf')
    else:
        mid = (a + b) // 2
        lvalue = query(a, mid, 2 * k + 1, l, r)
        rvalue = query(mid, b, 2 * k + 2, l, r)
        return min(lvalue, rvalue)

ans = 0
for l in range(N):
    for r in range(l, N):
        ans += query(0, N, 0, l, r + 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(raw_input())
a=map(int,raw_input().split())
b=sorted([(a[i],i+1) for i in range(n)])
s=[0,n+1]
ans=0
for c,j in b:
    k=bisect.bisect(s,j)
    ans+=c*(s[k]-j)*(j-s[k-1])
    s.insert(k,j)
print ans

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(raw_input())
a=map(int,raw_input().split())
b=sorted([(a[i],i+1) for i in range(n)])
s=[0,n+1]
ans=0
for c,j in b:
    k=bisect.bisect(s,j)
    ans+=c*(s[k]-j)*(j-s[k-1])
    bisect.insort(s,j)
print ans

Submission status: Time Limit Exceeded

Solution code:
n = input()
a = map(int, raw_input().split())
sum = 0
for i in xrange(n):
    k = 0
    while a[i] <= a[i-k]:
        k += 1
        if 0 > i-k or i-k >=n:
            break
    l = 0
    while a[i] <= a[i+l]:
        l += 1
        if 0 > i+l or i+l >=n:
            break
    sum += k*l*a[i]
    # print k,l,a[i]
print sum

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

s = 0
for i in range(n):
    l = 0
    m = 0
    while a[i] <= a[i-l]:
        l += 1
        if i-l+1 == 0:
            break
    while a[i] <= a[i+m]:
        m += 1
        if i+m == n:
            break
    s += a[i] * l*m

print s

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

s = long(0)
for i in range(n):
    for j in range(i,n):
        s += min(a[i:j+1])

print s

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())

s = 0
for i in range(n):
    for j in range(i,n):
        s += min(a[i:j+1])

print s

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a=[int(i) for i in input().split()]
s=[]
sa=n*(n+1)/2

s.append(a)
for i in range(1,n):
  s.append([])
  for j in range(len(s[i-1])-1):
    if s[i-1][j]<s[i-1][j+1]:
        s[i].append(s[i-1][j])
        sa+=s[i-1][j]
    else:
        s[i].append(s[i-1][j+1])
        sa+=s[i-1][j+1]
print(int(sa))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))

def resolve(a):
    target = N
    result = 0
    for i in a:
        if target > i:
            target = i
            result += i
        else:
            result += target
    return result

print(sum([resolve(a[x:]) for x in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
score = 0
for k in range(0,n):
	for l in range(k,n):
		score += min(a[k:l+1])
print(score)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from __future__ import unicode_literals


if __name__ == "__main__":
    n = int(raw_input(""))
    a = map(int, raw_input("").split(" "))
    c = 0
    for l in xrange(len(a)):
        for r in xrange(l, len(a)):
            c += min(a[l:r+1])
    print c

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    b = [0]*n
    for _ in range(n):
        b[a[_]-1] = _
    r = (b[0]+1) * (n-b[0])
    c = [b[0]]
    m = 2
    for i in b[1:]:
        ri = bisect.bisect(c, i)
        if ri == 0:
            r += (i+1) * (c[ri]-i) * m
        elif ri == m-1:
            r += (i-c[ri-1]) * (n-i) * m
        else:
            r += (i-c[ri-1]) * (c[ri]-i) * m
        m += 1
        c = c[:ri] + [i] + c[ri:]

    return r

print(f())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    b = [0]*n
    for _ in range(n):
        b[a[_]-1] = _
    r = (b[0]+1) * (n-b[0])
    c = [b[0]]
    m = 2
    for i in b[1:]:
        ri = bisect.bisect(c, i)
        if ri == 0:
            r += (i+1) * (c[ri]-i) * m
        elif ri == m-1:
            r += (i-c[ri-1]) * (n-i) * m
        else:
            r += (i-c[ri-1]) * (c[ri]-i) * m
        m += 1
        bisect.insort(c, i)

    return r

print(f())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**10
mod = 10**9 + 7

def f():
    n = int(input())
    a = list(map(int, input().split()))
    b = [a.index(_) for _ in range(1,n+1)]
    r = (b[0]+1) * (n-b[0])
    c = [b[0]]
    m = 2
    for i in b[1:]:
        ri = bisect.bisect(c, i)
        if ri == 0:
            r += (i+1) * (c[ri]-i) * m
        elif ri == m-1:
            r += (i-c[ri-1]) * (n-i) * m
        else:
            r += (i-c[ri-1]) * (c[ri]-i) * m
        m += 1
        bisect.insort(c, i)

    return r

print(f())

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
n = map(int, raw_input().split())

n_min = min(n)

total = 0
for ind, num in enumerate(n):
    if num == n_min:
        total += num * (ind+1) * (N - ind)
        continue

    l, k = ind, ind

    while l >= 0:
        if num <= n[l]:
            l -= 1
        else:
            break

    while k < N:
        if num <= n[k]:
            k += 1
        else:
            break

    total += num * (ind-l) * (k-ind)

print total

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
n = map(int, raw_input().split())

total = 0
for ind, num in enumerate(n):
    i, j = 0, 0
    l, k = ind, ind
    while l >= 0:
        if num <= n[l]:
            i += 1
            l -= 1
        else:
            break

    while k < N:
        if num <= n[k]:
            j += 1
            k += 1
        else:
            break

    total += num * (i * j)

print total

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
n = map(int, raw_input().split())

total = 0
for ind, num in enumerate(n):
    n1 = n[:ind+1][::-1]
    n2 = n[ind:]
    i,j=0,0
    l = ind
    while i<len(n1):
        if num <= n1[i]:
            i+=1
        else:
            break

    while j<len(n2):
        if num <= n2[j]:
            j+=1
        else:
            break

    total+=num*(i*j)

print total

Submission status: Time Limit Exceeded

Solution code:
import sys 
import numpy as np

N = int(sys.stdin.readline())
P = np.array([int(x) for x in sys.stdin.readline().split()])

SUM = np.sum([np.sum([np.min(P[l:r+1]) for r in range(l, N)]) for l in range(N)])

print(SUM)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n = int(input())
xs = np.array(list(map(int, input().split())))
idx = np.argsort(xs)+1
Ms = np.zeros(n, dtype=np.int64)
ms = np.ones(n, dtype=np.int64)*n

s = 0
for i in range(n):
    j = idx[i]
    l = Ms[j-1]
    b = ms[j-1]
    if l<j and b>=j:
        s += (j-l)*(b-j+1)*(i+1)
        Ms[j-1:b] = j
        ms[l:j] = j-1
print(s)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
array = list(map(int, input().split())) 
sum = 0
for l in range(N):

       for r in range(N):
              if r+1+l>N:
                     break
#==============================================================================
#               
#               print(l,r+l+1)
#               print( array[l:r+l+1])
#==============================================================================
              sum = sum + min(array[l:r+l+1])
print(sum)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = list(map(int, input().split()))

def resolve(a):
    target = N
    result = 0
    for i in a:
        if target > i: target = i
        result += target
    return result

print(sum([resolve(a[x:]) for x in range(N)]))

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
L = []
args = [0 for _ in range(N + 1)]
for i, a in enumerate(A):
    args[a] = i + 1
ans = 0
for n in range(1, N + 1):
    if n == 1:
        ans += args[n] * (N - args[n] + 1)
        L.append(args[n])
    else:
        ins = bisect.bisect_left(L, args[n])
        if ins == 0:
            l = args[n]
        else:
            l = args[n] - L[ins-1]
        if ins == n - 1:
            r = N - args[n] + 1
        else:
            r = L[ins] - args[n]
        # print(n, ins, l, r)
        ans += l * r * n
        # bisect.insort_left(L, args[n])
        L += [args[n]]
        L.sort()
print(ans)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())
ints = input().split()


int_list = [0] + [int(i) for i in ints]


total = 0

for l in range(1, N+1): # from 0 to N - 1
    running_sum = 0
    for r in range(l, N+1): # from 0 to N - 1
        permutation = int_list[l:r+1] # 1st element to rth element 
        running_sum += min(permutation)
              
    total += running_sum

print(total)

Submission status: Time Limit Exceeded

Solution code:
N = int(raw_input())
n = map(int, raw_input().split())

total = 0
for ind, num in enumerate(n):
    n1 = n[:ind+1]
    n2 = n[ind:]
    i,j=0,0
    while n1:
        if num <= n1.pop():
            i+=1
        else:
            break

    while n2:
        if num <= n2.pop(0):
            j+=1
        else:
            break

    total+=num*(i*j)

print total

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
L = []
args = [0 for _ in range(N + 1)]
for i, a in enumerate(A):
    args[a] = i + 1
ans = 0
for n in range(1, N + 1):
    if n == 1:
        ans += args[n] * (N - args[n] + 1)
        L.append(args[n])
    else:
        ins = bisect.bisect_left(L, args[n])
        if ins == 0:
            l = args[n]
        else:
            l = args[n] - L[ins-1]
        if ins == n - 1:
            r = N - args[n] + 1
        else:
            r = L[ins] - args[n]
        # print(n, ins, l, r)
        ans += l * r * n
        # bisect.insort_left(L, args[n])
        L.append(args[n])
        L.sort()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N = int(input())
a = input().split(" ")


it = itertools.combinations_with_replacement(sorted(a),2)
l = []
ans = 0
for i in it:
    ans += int(min(a[int(i[0])-1:int(i[1])]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
L = []
args = [0 for _ in range(N + 1)]
for i, a in enumerate(A):
    args[a] = i + 1
ans = 0
for n in range(1, N + 1):
    if n == 1:
        ans += args[n] * (N - args[n] + 1)
        L.append(args[n])
    else:
        ins = bisect.bisect_left(L, args[n])
        if ins == 0:
            l = args[n]
        else:
            l = args[n] - L[ins-1]
        if ins == n - 1:
            r = N - args[n] + 1
        else:
            r = L[ins] - args[n]
        # print(n, ins, l, r)
        ans += l * r * n
        bisect.insort_left(L, args[n])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
z=[(0,0)]*n
for ix,a in enumerate(arr):
    z[a-1]=(a,ix+1)
#print(z)
#z = sorted(list(zip(arr,list(range(1,n+1)))))
brr = [0]*(n+2)
brr[0]=1
brr[-1]=1
ans=0
for p in z:
    sm=0
    for i in range(p[1],-1,-1):
        if brr[i]==1:
            sm=i
            break
    lg=n+1
    for i in range(p[1],n+2):
        if brr[i]==1:
            lg=i
            break
    ans+=(lg-p[1])*(p[1]-sm)*p[0]
    brr[p[1]]=1
print(ans)