Problem:
 Score : 400 points    Problem Statement Snuke lives in another world, where slimes are real creatures and kept by some people.
Slimes come in N colors. Those colors are conveniently numbered 1 through N .
Snuke currently has no slime. His objective is to have slimes of all the colors together.  Snuke can perform the following two actions:    Select a color i ( 1≤i≤N ), such that he does not currently have a slime in color i , and catch a slime in color i . This action takes him a_i seconds.    Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i ( 1≤i≤N-1 ) will become color i+1 , and the color of a slime in color N will become color 1 . This action takes him x seconds.    Find the minimum time that Snuke needs to have slimes in all N colors.      Constraints  2≤N≤2,000  a_i are integers.  1≤a_i≤10^9  x is an integer.  1≤x≤10^9         Input The input is given from Standard Input in the following format:  N  x  a_1  a_2  ...  a_N       Output Find the minimum time that Snuke needs to have slimes in all N colors.        Sample Input 1 2 10
1 100      Sample Output 1 12  Snuke can act as follows:   Catch a slime in color 1 . This takes 1 second.  Cast the spell. The color of the slime changes: 1 → 2 . This takes 10 seconds.  Catch a slime in color 1 . This takes 1 second.        Sample Input 2 3 10
100 1 100      Sample Output 2 23  Snuke can act as follows:   Catch a slime in color 2 . This takes 1 second.  Cast the spell. The color of the slime changes: 2 → 3 . This takes 10 seconds.  Catch a slime in color 2 . This takes 1 second.  Cast the soell. The color of each slime changes: 3 → 1 , 2 → 3 . This takes 10 seconds.  Catch a slime in color 2 . This takes 1 second.        Sample Input 3 4 10
1 2 3 4      Sample Output 3 10  Snuke can act as follows:   Catch a slime in color 1 . This takes 1 second.  Catch a slime in color 2 . This takes 2 seconds.  Catch a slime in color 3 . This takes 3 seconds.  Catch a slime in color 4 . This takes 4 seconds.

Solution (Python):

class SegTree():
    
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, X = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(3*N)]
for i in range(N):
    B[i] = B[i+N] = B[i+2*N] = A[i]

T = SegTree(B, min, 10**10)
ans = 10**30


for cnt in range(N+1):
    
    
    sub = X*cnt
    for i in range(1+N, 2*N+1):
        sub += T.query(i-cnt, i+1)
    ans = min(sub, ans)
print(ans)

Solution (Python):

class SegTree():
    
    def __init__(self, lists, function, basement):
        self.n = len(lists)
        self.K = (self.n-1).bit_length()
        self.f = function
        self.b = basement
        self.seg = [basement]*(2**(self.K+1)+1)
        X = 2**self.K
        for i, v in enumerate(lists):
            self.seg[i+X] = v
        for i in range(X-1, 0, -1):
            self.seg[i] = self.f(self.seg[i << 1], self.seg[i << 1 | 1])

    def update(self, k, value):
        X = 2**self.K
        k += X
        self.seg[k] = value
        while k:
            k = k >> 1
            self.seg[k] = self.f(self.seg[k << 1], self.seg[(k << 1) | 1])

    def query(self, L, R):
        num = 2**self.K
        L += num
        R += num
        vL = self.b
        vR = self.b
        while L < R:
            if L & 1:
                vL = self.f(vL, self.seg[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.seg[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)


N, X = map(int, input().split())
A = list(map(int, input().split()))
B = [0 for i in range(3*N)]
for i in range(N):
    B[i] = B[i+N] = B[i+2*N] = A[i]

T = SegTree(B, min, 10**10)
ans = 10**30


for cnt in range(N+1):
    
    
    sub = X*cnt
    for i in range(1+N, 2*N+1):
        sub += T.query(i, i+1+cnt)
    ans = min(sub, ans)
print(ans)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, X = map(int, readline().split())
A = np.array(read().split(), np.int64)

INF = 10**18
dp = np.full((N, N + N), INF, np.int64)
dp[0] = np.concatenate((A, A))
for n in range(1, N):
    dp[n, 1:] = np.minimum(dp[n - 1, 1:], dp[n - 1, :-1])
dp = dp[:, N:]

x = dp.sum(axis=1) + X * np.arange(N)
print(x.min())

Solution (Python):
n, k = map(int, input().split())
a = tuple(map(int, input().split()))

inf = 10 ** 13
res = inf
b = [inf] * n

for x in range(n):
    bsum = 0
    for i in range(n):
        j = (i - x) % n
        b[i] = min(b[i], a[j])
        bsum += b[i]
    res = min(res, k * x + bsum)

print(res)

Solution (Python):
INF = 2**31-1
class segtree():
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.data = [INF]*((2*self.N0)+1)

    
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    
    def get(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
    
N, x = map(int,input().split())

s_tree = segtree(2*N) 
arr = list(map(int,input().split()))

for i in range(N):
    s_tree.update(i, arr[i])
    s_tree.update(i+N, arr[i])

ans = float("inf")
for i in range(N):
    tmp = i * x
    for k in range(N,2*N):
        tmp += s_tree.get(k-i,k+1)
    ans = min(ans,tmp) 
    
print(ans)

Solution (Python):

N,x = map(int,input().split())
A = list(map(int,input().split()))
B = A[:]
ans = sum(A)
for k in range(1,N):
    for i in range(N):
        B[i] = min(B[i],A[(i-k)%N])
    ans = min(ans,sum(B)+k*x)
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



from queue import deque
n,x = map(int, input().split())
A = list(map(int, input().split()))

def sub(p):
    k = p
    res = []
    q = deque([])
    a = A + A[:k-1]
    
    for i,num in enumerate(a):
        while q and a[q[-1]]>num:
            q.pop()
        q.append(i)
        if q[0]<=i-k:
            q.popleft()
        if i>=k-1:
            m = a[q[0]] 
            res.append(m)
    return sum(res)


ans = 10**15
for p in range(n):
    ans = min(ans, sub(p+1) + x*p)
print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")



from queue import deque
n,x = map(int, input().split())
a = list(map(int, input().split()))

def sub(p):
    k = p
    res = []
    q = deque([])
    
    for i,num in enumerate(a):
        while q and a[q[-1]]>num:
            q.pop()
        q.append(i)
        if q[0]<=i-k:
            q.popleft()
        if i>=k-1:
            m = a[q[0]] 
            res.append(m)
    for j,num in enumerate(a):
        if len(res)>=n:
            break
        while q and a[q[-1] if q[-1]<n else q[-1]-n]>num:
            q.pop()
        q.append(j+n)
        if q[0]<=j+n-k:
            q.popleft()
        m = a[q[0] if q[0]<n else q[0]-n] 
        res.append(m)
    return sum(res)


ans = 10**15
for p in range(n):
    ans = min(ans, sub(p+1) + x*p)
print(ans)

Solution (Python):
n,x=map(int,input().split())
A=list(map(int,input().split()))
ans=float("INF")
dp=[[A[i]]*n for i in range(n)]
for l in range(n):
  a=A[l:]+A[:l]
  a=a[::-1]
  for i in range(n-1):
    dp[l][i+1]=min(dp[l][i],a[i])
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=dp[j][i]
  ans=min(tmp+x*i,ans)
print(ans)

Solution (Python):
N,x = map(int,input().split())
a = list(map(int,input().split()))
res = 10**18
d = [[0]*N for _ in range(N)]
for i in range(N):
    d[i][0] = a[i]
    for k in range(1,N):
        d[i][k] = min(d[i][k-1], a[i-k])

for k in range(N-1,-1,-1):
    tmp = k*x
    tmp += sum([d[i][k] for i in range(N)])
    res = min(res,tmp)
print(res)

Solution (Python):
INF = 2**31-1
class SegmentTree():
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.data = [INF]*((2*self.N0)+1)

    
    def update(self, k, x):
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = min(self.data[2*k+1], self.data[2*k+2])

    
    def query(self, l, r):
        L = l + self.N0; R = r + self.N0
        s = INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])

            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s


n, x = map(int, input().split())
a = list(map(int, input().split()))
ans = 10**18
segtree = SegmentTree(2*n)
for i in range(n):
    segtree.update(i, a[i])
    segtree.update(i+n, a[i])


for k in range(n):
    temp = k*x
    for i in range(n, 2*n):
        temp += segtree.query(i-k, i+1)
    ans = min(ans, temp)

print(ans)

Solution (Python):
def main():
  N, x = map(int, input().split())
  a = list(map(int, input().split()))
  c = [a[i] for i in range(N)]
  ans = sum(a)
  for i in range(N):
    tmp = i*x
    for j in range(N):
      c[j]=min(c[j],a[j-i])
      tmp += c[j]
    ans=min(ans,tmp)
  print(ans)
main()

Solution (Python):
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=a[:]
ans=10**20
for i in range(n):
    for j in range(n):
        b[j]=min(b[j],a[j-i])
    ans=min(ans,sum(b)+x*i)
print(ans)

Solution (Python):

import sys
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(A[Q[0]])
    return res[K - 1:]


N, X = lr()
A = lr()
INF = 10 ** 15
A += A
answer = INF
for t in range(N):
    temp = t * X
    mi = slide_min(A, t + 1)
    mi = mi[N-t:]
    temp += sum(mi)
    if temp < answer:
        answer = temp

print(answer)

Solution (Python):
n, x = map(int, input().split())
a = list(map(int, input().split()))
b = a[:]

ans = sum(a)
for k in range(1, n):
  for i in range(n):
    if b[i] > a[i-k]:
      b[i] = a[i-k]
  ans = min(ans, sum(b) + k*x)
print(ans)

Solution (Python):
from itertools import accumulate
from functools import reduce
N,x,*A = map(int, open(0).read().split())
dp =[list(accumulate((A[i-j] for j in range(N)),min)) for i in range(N)]
ans = reduce(min, (i*x+sum(a) for i,a in enumerate(zip(*dp))))
print(ans)

Solution (Python):
from itertools import accumulate
from functools import reduce
N,x,*A = map(int, open(0).read().split())
dp = [0]*N
for i in range(N):
  dp[i] = list(accumulate((A[i-j] for j in range(N)),min))
ans = reduce(min, (i*x+sum(a) for i,a in enumerate(zip(*dp))))
print(ans)

Solution (Python):
N, X = map(int, input().split())
A = list(map(int, input().split()))
B = A[:]

ans = sum(A)
for x in range(1, N + 1):
    for i in range(N)[::-1]:
        if B[i] > A[i - x]:
            B[i] = A[i - x]
    ans = min(ans, sum(B) + x * X)
print(ans)

Solution (Python):
from collections import deque

class SlideMin:
    """
    スライド最小値\n
    各区間[ai, ai+leng]の最小値を取得する：O(n)\n
    self.que = [(i1, v1), (i2, v2), ..., (ik, vk)]\n
    i1 < ... < ik and v1 < ... < vk
    """
    def __init__(self, leng):
        self.que = deque([])
        self.leng = leng

    def top(self):
        return self.que[0]

    def getQue(self):
        return self.que

    def update(self, index, value):
        while self.que:
            if self.que[-1][1] >= value:
                self.que.pop()
            else:
                break

        self.que.append((index, value))

        if self.que[0][0] == index - self.leng:
            self.que.popleft()

N, X = map(int, input().split())
A = list(map(int, input().split()))

def sol(n):
    
    B = A + A
    que = SlideMin(n + 1)
    ret = [10**18] * N
    for i, a in enumerate(B):
        que.update(i, a)
        ret[i % N] = min(ret[i % N], que.top()[1])
    return sum(ret) + n * X

ans = sum(A)
for i in range(N):
    ans = min(ans, sol(i))
print(ans)

Solution (Python):
N, x = map(int, input().split())
A = list(map(int, input().split()))

min_time = [a for a in A]
ans = 10**15
for t in range(N):
  time = t*x
  for i in range(N):
    j = (i - t) % N
    min_time[i] = min(min_time[i], A[j])
    time += min_time[i]
  ans = min(ans, time)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, x = map(int, input().split())
a = list(map(int, input().split()))
INF = 10**18
cost = [[INF] * N for _ in range(N)]
for i in range(N):
    cost[i][0] = a[i]
    for j in range(1, N):
        k = (i - j) % N
        cost[i][j] = min(a[k], cost[i][j - 1])
total = [sum(cost[i][j] for i in range(N)) for j in range(N)]
print(min(total[i] + x * i for i in range(N)))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        return res


def solve():
    N, x = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    seg_tree = SegmentTree(a, min, 10 ** 15)
    ans = 10 ** 15
    for i in range(N):
        get_cost = 0
        for j in range(N):
            if i <= j:
                get_cost += seg_tree.query(j - i, j + 1)
            else:
                get_cost += min(seg_tree.query(0, j + 1), seg_tree.query(N - i + j, N))
        ans = min(ans, i * x + get_cost)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys


class SegTreeMin:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.get_min: 区間[l, r)の最小値を得る
    """

    def __init__(self, n, INF):
        """
        :param n: 要素数
        :param INF: 初期値（入りうる要素より十分に大きな数）
        """
        n2 = 1 << (n - 1).bit_length()
        self.offset = n2
        self.tree = [INF] * (n2 << 1)
        self.INF = INF

    @classmethod
    def from_list(cls, lst, INF):
        """
        既存のリストから構築する

        :param lst:
        :param INF:
        :return:
        """
        n = len(lst)
        ins = cls(n, INF)
        ofs = ins.offset
        tree = ins.tree
        tree[ofs:ofs + n] = lst
        for i in range(ofs - 1, 0, -1):
            l = i << 1
            tree[i] = min(tree[l], tree[l + 1])
        return ins

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.offset
        self.tree[i] = x
        while i > 1:
            y = self.tree[i ^ 1]
            if y <= x:
                break
            i >>= 1
            self.tree[i] = x

    def get_min(self, a, b):
        """
        [a, b)の最小値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        result = self.INF

        l = a + self.offset
        r = b + self.offset
        while l < r:
            if r & 1:
                result = min(result, self.tree[r - 1])
            if l & 1:
                result = min(result, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1

        return result


n, x, *aaa = map(int, sys.stdin.buffer.read().split())
INF = 10 ** 18
sgt = SegTreeMin.from_list(aaa + aaa, INF)

ans = INF
for k in range(n):
    ans = min(ans, sum(sgt.get_min(i - k, i + 1) for i in range(n, 2 * n)) + k * x)
print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,x = na()
a = na()
dp = [i for i in a]
ans = sum(dp)

for i in range(1,n):
    for j in range(n):
        dp[(j+i)%n] = min(dp[(j+i)%n], a[j])
    ans = min(ans, sum(dp)+x*i)

print(ans)

Solution (Python):
n,x = map(int,input().split())
A = list(map(int,input().split()))
inf = float('inf')
ans = inf
dp = [[inf]*n for i in range(n)]
for i in range(n):
    cnt = x*i
    for j in range(n):
        if i == 0:
            dp[i][j] = A[j]
        cnt += dp[i][j]
        if i != n-1:
            dp[i+1][(j+1)%n] = min(dp[i+1][(j+1)%n],dp[i][j])
            dp[i+1][j] = min(dp[i+1][j],dp[i][j])
    ans = min(ans,cnt)
print(ans)

Solution (Python):
N, X, *A = map(int, open(0).read().split())

ans = sum(A)
b = A[:]
for k in range(1, N):
    for i in range(N):
        b[i] = min(b[i], A[i - k])
    ans = min(ans, k * X + sum(b))
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import copy

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = copy.deepcopy(a)
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def main():
    N,x = map(int,input().split())
    a = list(map(int,input().split()))
    b = a.copy()
    
    ans = 10**15
    for i in range(N):
        time = i*x+sum(b)
        ans = min(ans,time)
        for now in range(N):
            b[now] = min(b[now],a[(now-i-1+N)%N])

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
n, x = map(int, input().split())
a = list(map(int, input().split()))


minrange = [[0 for j in range(n)] for i in range(n)]
for r in range(n):
    for l in range(r):
        minrange[l][r] = min(minrange[l][r-1], a[r])
    minrange[r][r] = a[r]

res = int(1e18) 
for k in range(n):
    cur = k*x
    for i in range(n):
        if i-k >= 0:
            cur += minrange[i-k][i]
        else:
            cur += min(minrange[0][i], minrange[i-k+n][n-1])
    res = min(res, cur)

print(res)

Solution (Python):
import copy

n,x = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
now = a.copy()
for i in range(1,n):
  for j in range(n):
    now[j] = min(now[j],a[(j+i)%n])
  ans = min(ans,sum(now) + x * i)
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class Segtree:
    def __init__(self, A, ide_ele, segfunc, initialize=True):
        self.n = len(A)
        self.size = 2 ** (self.n - 1).bit_length()
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        if initialize:
            self.data = [ide_ele] * self.size + A + [ide_ele] * (self.size - self.n)
            for i in range(self.size - 1, 0, -1):
                self.data[i] = self.segfunc(self.data[2 * i], self.data[2 * i + 1])
        else:
            self.data = [ide_ele] * (2 * self.size)

    def update(self, k, x):
        k += self.size
        self.data[k] = x
        while k:
            k = k >> 1
            self.data[k] = self.segfunc(self.data[2 * k], self.data[2 * k + 1])

    def query(self, l, r):
        L, R = l + self.size, r + self.size
        s = self.ide_ele
        while L < R:
            if R & 1:
                R -= 1
                s = self.segfunc(s, self.data[R])
            if L & 1:
                s = self.segfunc(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

n, x = LI()
A = LI()
ans = INF
seg = Segtree(A, INF, min)
for i in range(n):
    ret = i * x
    for j in range(n):
        if j - i >= 0:
            ret += seg.query(j - i, j + 1)
        else:
            ret += min(seg.query(0, j + 1), seg.query(n - (i - j), n))
    ans = min(ans, ret)


print(ans)

Solution (Python):
import sys

rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k >>= 1
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        return res


def solve():
    N, x = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    seg_tree = SegmentTree(a, min, 10 ** 15)
    ans = 10 ** 15
    for i in range(N):
        get_cost = 0
        for j in range(N):
            if i <= j:
                get_cost += seg_tree.query(j - i, j + 1)
            else:
                get_cost += min(seg_tree.query(0, j + 1), seg_tree.query(N - i + j, N))
        ans = min(ans, i * x + get_cost)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys

rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.N0 - 1
        self.data[k] = x
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        return res


def solve():
    N, x = map(int, rl().split())
    a = list(map(int, rl().split()))
    
    seg_tree = SegmentTree(a, min, 10 ** 15)
    ans = 10 ** 15
    for i in range(N):
        get_cost = 0
        for j in range(N):
            if i <= j:
                get_cost += seg_tree.query(j - i, j + 1)
            else:
                get_cost += min(seg_tree.query(0, j + 1), seg_tree.query(N - i + j, N))
        ans = min(ans, i * x + get_cost)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
n, x = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [10 ** 10] * n
ans = 10 ** 18
for i in range(n):
    for j in range(n):
        b[j] = min(b[j], a[(j - i) % n])
    ans = min(ans, sum(b) + x * i)
print(ans)

Solution (Python):
n, x = map(int, input().split())
A = list(map(int, input().split()))
memo = A[:]
ans = sum(memo)
for k in range(1, n):
  memo = [min(m, A[itr - k]) for itr, m in enumerate(memo)] 
  ans = min(ans, sum(memo) + x * k)
print(ans)

Solution (Python):
n,x = map(int, input().split())
a = list(map(int, input().split()))
cost = a[:]
ans = sum(a)
for k in range(1,n):
  sc = k*x
  for i in range(n):
    if cost[i] > a[i-k]: cost[i] = a[i-k]
    sc += cost[i]
  if sc < ans: ans = sc
print(ans)

Solution (Python):
from collections import deque

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

def slide(a, k):
  q = deque()
  ans = 0
  for i in range(-k,0):
    while q and a[q[-1]] > a[i]: q.pop()
    q.append(i)
  for i in range(n):
    if q[0] <= i-k: q.popleft()
    while q and a[q[-1]] > a[i]: q.pop()
    q.append(i)
    ans += a[q[0]]
  return ans

print(min(slide(a,k+1) + x*k for k in range(n)))

Solution (Python):
from itertools import accumulate as acc
N, x, *A = map(int, open(0).read().split())
dp = []
for i in range(N):
  dp.append(list(acc((A[(i-j)%N] for j in range(N)),min)))

ans = 10**60
for i,a in enumerate(zip(*dp)):
  ans = min(ans,i*x+sum(a))
print(ans)

Solution (Python):
""" 解答AC """

N,x = map(int,input().split())
a = [int(i) for i in input().split()]


b = a.copy()

ans = float("inf")

for k in range(N):
    for i in range(N):
        b[i] = min(b[i], a[(i - k) % N])

    ans = min(ans, k * x + sum(b))

print(ans)

Solution (Python):
import numpy as np

n, x = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int32)

rec = np.zeros((n, n), dtype=np.int32)
for i in range(n):
    a_tmp = np.roll(np.flipud(a), i)
    np.minimum.accumulate(a_tmp, out=rec[i])

ans = float("inf")
for j in range(n):
    second = rec[:, j].sum() + j * x
    ans = min(ans, second)

print(ans)

Solution (Python):
import numpy as np

n, x = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int32)

rec = np.zeros((n, n), dtype=np.int32)
for i in range(n):
    a_tmp = np.concatenate([a[i::-1], a[-1:i:-1]])
    np.minimum.accumulate(a_tmp, out=rec[i])

ans = float("inf")
for j in range(n):
    second = rec[:, j].sum() + j * x
    ans = min(ans, second)

print(ans)

Solution (Python):
N,x=map(int,input().split())
a=list(map(int,input().split()))
data=[10**20 for i in range(0,N)]
ans=10**20
test=0
for i in range(0,N):
    flag=0
    for j in range(0,N):
        if a[j-i]<data[j]:
            data[j]=a[j-i]
            flag=1
    if flag==1:
        test=sum(data)+x*i
        if test<ans:
            ans=test

print(ans)

Solution (Python):



n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = sum(m)

for k in range(n):
    
    for i in range(n,2*n):
        m[i-n] = min(m[i-n], a[i-k])
        
    min_cost = min(min_cost, x*k + sum(m))
print(min_cost)

Solution (Python):



n,x =  [int(i) for i in input().split()]
a   =  [int(i) for i in input().split()]
m   =  a[::]
a.extend(a)

min_cost = sum(a)

for k in range(n):
    
    for i in range(n,2*n):
        m[i-n] = min(m[i-n], a[i-k])
        
    min_cost = min(min_cost, x*k + sum(m))
print(min_cost)

Solution (Python):
n, x = map(int,input().split())
A = list(map(int,input().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)

Solution (Python):
n, x = map(int,input().split())
A = list(map(int,input().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)

Solution (Python):
import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)

Solution (Python):
""" 解答AC """

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

ans = float("inf")


b = a.copy()


for k in range(N):
    for i in range(N):
        b[i] = min(b[i], a[(i-k) % N])

    ans = min(ans, k * x + sum(b))

print(ans)

Solution (Python):
def main():
    n, x = map(int, input().split())
    a = list(map(int, input().split()))
    ans = 1100100100100100100
    mina = [10000000000 for i in range(n)]
    for i in range(n):
        for j in range(n):
            mina[j] = min(mina[j], a[i - j])
        sumb = sum(mina)
        ans = min(ans, sumb + i * x)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,x=map(int,input().split())
a=list(map(int,input().split()))
b=[ai for ai in a]
res=sum(b)
for i in range(1,n):
  for j in range(n):
    b[(i+j)%n]=min(b[(i+j)%n],a[j])
  res=min(res,sum(b)+x*i)
print(res)