Problem:


Score: 500 points

Problem Statement

Given is a permutation P of \{1, 2, \ldots, N\}.

For a pair (L, R) (1 \le L \lt R \le N), let X_{L, R} be the second largest value among P_L, P_{L+1}, \ldots, P_R.

Find \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Constraints

 2 \le N \le 10^5 

 1 \le P_i \le N 

 P_i \neq P_j  (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
P_1 P_2 \ldots P_N

Output

Print \displaystyle \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}.

Sample Input 1

3
2 3 1

Sample Output 1

5

X_{1, 2} = 2, X_{1, 3} = 2, and X_{2, 3} = 1, so the sum is 2 + 2 + 1 = 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

30

Sample Input 3

8
8 2 7 3 4 5 6 1

Sample Output 3

136



Sample input:
3
2 3 1


Sample output:
5

Submission status: Accepted

Solution code:
class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        # for i in range(len(A)):
        #     self.__node[i + n] = A[i]
        # for i in range(n - 1, 0, -1):
        #     self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 0:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


def solve():
    N = int(input())
    P = map(int, input().split())
    plist = []
    for i, p in enumerate(P):
        plist.append((p, i))
    plist.sort(reverse=True)

    maxSeg = SegmentTree([-1] * N, max, -1)
    minSeg = SegmentTree([N] * N, min, N)

    cnt = 0
    for p, c in plist:
        l2 = maxSeg.get(0, c)
        l1 = -1 if l2 <= 0 else maxSeg.get(0, l2)

        r1 = minSeg.get(c + 1, N)
        r2 = N if r1 >= N - 1 else minSeg.get(r1 + 1, N)

        a = (l2 - l1) * (r1 - c)
        b = (r2 - r1) * (c - l2)
        cnt += p * (a + b)

        maxSeg.update(c, c)
        minSeg.update(c, c)

    print(cnt)


solve()

Submission status: Accepted

Solution code:

# 1-indexed　Binary Indexed Tree
class BIT:
    def __init__(self, n, init_list):
        self.num = n+1
        self.tree = [0]*self.num
        for i,e in enumerate(init_list):
            self.update(i,e)

    def update(self,k,x):
        k = k+1
        while k < self.num:
            self.tree[k] += x
            k += (k&(-k))
        return 
    
    # sum([l,r))
    def query(self, l,r):
        ret = 0
        while r>0:
            ret += self.tree[r]
            r -= r&(-r)
        while l>0:
            ret -= self.tree[l]
            l -= l&(-l)
        
        return ret


N = int(input())
A = list(map(int,input().split()))
#%%
idxlist = [0]*N
for i,a in enumerate(A):
    idxlist[a-1] = i+2

A = [N+1]*2 + A + [N+1]*2
#%%
ans = 0
seg = BIT(N+4,[1]*2+[0]*N+[1]*2)

def judge(l,r,key):
    if l>r:
        l,r = r,l
    res = seg.query(l,r+1)
    if res>key:
        return False
    else:
        return True

def bsearch(idx,ng,key):
    ok = idx
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if judge(idx,mid,key):
            ok = mid
        else:
            ng = mid
    return ng


for idx in reversed(idxlist):
    if A[idx]==N:
        seg.update(idx,1)
        continue
    ng_l = 0
    ng_r = N+3
    
    L1 = bsearch(idx,ng_l,0)
    L2 = bsearch(idx,ng_l,1)
    R1 = bsearch(idx,ng_r,0)
    R2 = bsearch(idx,ng_r,1)
    
    coef = 0
    if A[L1]!=N+1:
        coef += (L1-L2)*(R1-idx)
    if A[R1]!=N+1:
        coef += (R2-R1)*(idx-L1)
    ans += A[idx]*coef
    seg.update(idx,1)
    
print(ans)

Submission status: Accepted

Solution code:
#incited from https://juppy.hatenablog.com/entry/2019/02/26/python_AVL%E6%9C%A8_%E9%85%8D%E5%88%97ver_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder_
#AVL-Tree code by edamat

class Avltree:
    """
    AVL木
 
    Methods
    -------
        search(x: int) -> Union(int)
            ◯.data == x のものが存在するある場合それを出力、ない場合 None を返す
        insert(x: int) -> None
            ◯.data == x がない場合 ◯.data == x なる頂点を作る。ある場合はなにもしない（上書きしない）
        y.to_s() -> int
            頂点yのdataを返す
        y.left_s() -> Union(int, key=None)
            頂点yのleftを返す(ない場合は key)
        search_lower(x: int, key_lower) -> int
            ○.data が x より小さいものの中で最も大きいものを出力、ない場合 key_lower を返す
        search_higher(x:int , key_higher) -> int
            ○.data が x より大きいものの中で最も小さいものを出力、ない場合 key_higher を返す
    """
 
    def __init__(self, key=None):
        self.key = key
        self.left = None
        self.right = None
        self.balance = "Even"
 
    def search(self, key):
        node = self
        while node is not None:
            if node.key == key:
                return node  # node.key == keyの場合
            if node.key > key:
                node = node.left
            elif node.key < key:
                node = node.right
        return None
 
    def search_lower(self, key, key_lower):
        node = self
        if node.key is None:
            return key_lower
        ans = key_lower
        while node is not None:
            if node.key < key:
                if ans < node.key:
                    ans = node.key
                node = node.right
            elif node.key >= key:
                node = node.left
        return ans
 
    def search_higher(self, key, key_higher):
        node = self
        if node.key is None:
            return key_higher
        ans = key_higher
        while node is not None:
            if node.key > key:
                if ans > node.key:
                    ans = node.key
                node = node.left
            elif node.key <= key:
                node = node.right
        return ans
 
 
    def end_lower(self, end_lower_key):
        node = self
        while node.left is not None:
            node = node.left
        return node.key
 
    def end_higher(self, end_higher_key):
        node = self
        while node.right is not None:
            node = node.right
        return node.key
 
 
    def DoubleRightRotation(self):
        tl = self.left
        self.left = tl.right.right
        tl.right.right = self  # selfはそのノード
        tlr = tl.right
        tl.right = tlr.left
        tlr.left = tl
        if tlr.balance == "Left":
            tlr.right.balance = "Right"
            tlr.left.balance = "Even"
        elif tlr.balance == "Right":
            tlr.right.balance = "Even"
            tlr.left.balance = "Left"
        elif tlr.balance == "Even":
            tlr.right.balance = "Even"
            tlr.left.balance = "Even"
        tlr.balance = "Even"
        return tlr
    def DoubleLeftRotation(self):
        tr = self.right
        self.right = tr.left.left
        tr.left.left = self
        trl = tr.left
        tr.left = trl.right
        trl.right = tr
        if trl.balance == "Right":
            trl.left.balance = "Left"
            trl.right.balance = "Even"
        elif trl.balance == "Left":
            trl.left.balance = "Even"
            trl.right.balance = "Right"
        elif trl.balance == "Even":
            trl.left.balance = "Even"
            trl.right.balance = "Even"
        trl.balance = "Even"
        return trl
    def SingleLeftRotation(self):
        tr = self.right
        tr.balance = "Even"
        self.balance = "Even"
        self.right = tr.left
        tr.left = self
        return tr
    def SingleRightRotation(self):
        tl = self.left
        tl.balance = "Even"
        self.balance = "Even"
        self.left = tl.right
        tl.right = self
        return tl
    def replace(self, p, v):  # 親ノードpの下にある自分(self)をvに置き換える。
        if p.left == self:
            p.left = v
        else:
            p.right = v
    def insert(self, key):  # rootでのみ呼ばれる挿入
        if self.key is None:  # rootを含むrotationはしないことにする。
            self.key = key
            return self
        if key < self.key:
            if self.left is None:
                self.left = Avltree(key)
            else:
                self.left.insertx(self, key)
        elif key > self.key:
            if self.right is None:
                self.right = Avltree(key)
            else:
                self.right.insertx(self, key)
        else:  # key == self.key:
            pass  # do not overwrite
    def insertx(self, p, key):  # replaceを呼ぶために一つ上の親を持っているinsert
        node = self
        s = []
        while True:
            if node.key > key:
                s.append((node, -1))
                if node.left is None:
                    node.left = Avltree(key)
                    node = node.left
                    break
                else:
                    node = node.left
            elif node.key < key:
                s.append((node, 1))
                if node.right is None:
                    node.right = Avltree(key)
                    node = node.right
                    break
                else:
                    node = node.right
        while len(s) != 0:
            node, direct = s.pop()
            if len(s) != 0:
                par = s[-1][0]
            else:
                par = p
            if direct == -1:
                if node.balance == "Right":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Left"
                elif node.balance == "Left":
                    if node.left.balance == "Right":
                        node.replace(par, node.DoubleRightRotation())
                    elif node.left.balance == "Left":
                        node.replace(par, node.SingleRightRotation())
                    break
            elif direct == 1:
                if node.balance == "Left":
                    node.balance = "Even"
                    break
                elif node.balance == "Even":
                    node.balance = "Right"
                elif node.balance == "Right":
                    if node.right.balance == "Left":
                        node.replace(par, node.DoubleLeftRotation())
                    elif node.right.balance == "Right":
                        node.replace(par, node.SingleLeftRotation())
                    break
 
    def to_s(self):
        return self.key
    def left_s(self):
        if self.left is None:
            return None
        return (self.left).key
    def right_s(self):
        if self.right is None:
            return None
        return (self.right).key

n=int(input())
arr=list(map(int,input().split()))
arr2=[[arr[i],i+1] for i in range(n)]
arr2=sorted(arr2,reverse=True,key=lambda x:x[0])
avl=Avltree()
ans=0
avl.insert(0)
avl.insert(n+1)
for val,pos in arr2:
  fl=avl.search_lower(pos,0)
  if fl==0:
    sl=0
  else:
    sl=avl.search_lower(fl,0)
  fr=avl.search_higher(pos,n+1)
  if fr==n+1:
    sr=n+1
  else:
    sr=avl.search_higher(fr,n+1)
  cnt=(fl-sl)*(fr-pos)+(pos-fl)*(sr-fr)
  ans+=cnt*val
  avl.insert(pos)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right, insort_right
class SquareSkipList:
    def __init__(self, values=None, sorted_=False, square=1000, seed=42):
        # values: 初期値のリスト
        # sorted_: 初期値がソート済みであるか
        # square: 最大データ数の平方根
        # seed: 乱数のシード
        inf = float("inf")
        self.rand_y = seed
        self.square = square
        if values is None:
            self.layer1 = []
            self.layer0 = [[]]
        else:
            self.layer1 = layer1 = []
            self.layer0 = layer0 = []
            if not sorted_:
                values.sort()
            rand_depth = self.rand_depth
            l0 = []
            for v in values:
                if rand_depth():
                    layer0.append(l0)
                    l0 = []
                    layer1.append(v)
                else:
                    l0.append(v)
            layer0.append(l0)
        self.layer1.append(inf)

    def rand_depth(self):  # 32bit xorshift
        y = self.rand_y
        y ^= y << 13 & 0xffffffff
        y ^= y >> 17
        y ^= y << 5 & 0xffffffff
        self.rand_y = y
        return y % self.square == 0

    def add(self, x):  # 要素の追加
        layer1, layer0 = self.layer1, self.layer0
        if self.rand_depth():
            idx1 = bisect_right(layer1, x)
            layer1.insert(idx1, x)
            layer0_idx1 = layer0[idx1]
            idx0 = bisect_right(layer0_idx1, x)
            layer0.insert(idx1+1, layer0_idx1[idx0:])  # layer0 は dict で管理した方が良いかもしれない
            del layer0_idx1[idx0:]
        else:
            idx1 = bisect_right(layer1, x)
            insort_right(layer0[idx1], x)

    def remove(self, x):  # 要素の削除
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        if layer1[idx1] == x:
            del layer1[idx1]
            layer0[idx1] += layer0[idx1+1]
            del layer0[idx1+1]
        else:
            layer0_idx1 = layer0[idx1]
            del layer0_idx1[bisect_left(layer0_idx1, x)]

    def bisect_left(self, x):  # x 以上の最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        if res == x:
            return res
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_higher(self, x):  # x を超える最小の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_right(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if layer0_idx1:
            idx0 = bisect_right(layer0_idx1, x)
            if idx0 == len(layer0_idx1):
                return res
            else:
                return layer0_idx1[idx0]
        else:
            return res

    def search_lower(self, x):  # x 未満の最大の値を返す  O(log(n))
        layer1, layer0 = self.layer1, self.layer0
        idx1 = bisect_left(layer1, x)
        res = layer1[idx1]
        layer0_idx1 = layer0[idx1]
        if res != x:  # res > x
            if layer0_idx1:
                idx0 = bisect_left(layer0_idx1, x)
                if idx0 != 0:
                    return layer0_idx1[idx0-1]
            return layer1[idx1-1]  # layer0_idx1 が空の場合とすべて x 以上の場合
        else:
            idx0 = bisect_left(layer0_idx1, x)
            if idx0 == 0:  # layer0_idx1 が空の場合とすべて res で埋まっている場合
                return layer1[idx1-1]
            else:
                return layer0_idx1[idx0-1]

    def pop(self, idx):
        # 小さい方から idx 番目の要素を削除してその要素を返す（0-indexed）
        # O(sqrt(n))  for を回すので重め
        layer1, layer0 = self.layer1, self.layer0
        s = -1
        for i, l0 in enumerate(layer0):
            s += len(l0) + 1
            if s >= idx:
                break
        if s==idx:
            layer0[i] += layer0[i+1]
            del layer0[i+1]
            return layer1.pop(i)
        else:
            return layer0[i].pop(idx-s)

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

D = {P[i]:i+1 for i in range(N)}
ans = 0

L = SquareSkipList()
L.add(D[N])

for i in range(1,N)[::-1]:
    l = L.search_lower(D[i])
    h = L.search_higher(D[i])
    if l == float('inf'):
        hh = L.search_higher(h)
        if hh == float('inf'):
            hh = N+1
        ans += (D[i]*(hh-h))*i
    elif h == float('inf'):
        ll = L.search_lower(l)
        if ll == float('inf'):
            ll = 0
        ans += ((N+1-D[i])*(l-ll))*i
    else:
        hh = L.search_higher(h)
        if hh == float('inf'):
            hh = N+1
        ll = L.search_lower(l)
        if ll == float('inf'):
            ll = 0
        ans += ((h-D[i])*(l-ll)+(D[i]-l)*(hh-h))*i
    L.add(D[i])
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
P = list(enumerate(list(map(int, input().split()))))
P = sorted(P, key=lambda x:x[1])

before_idx = list(range(-1, N-1)) + [-1, -1]
next_idx = list(range(1, N+1)) + [N, N]
ans = 0
for i, p in P:
  il1 = before_idx[i]
  il2 = before_idx[il1]
  ir1 = next_idx[i]
  ir2 = next_idx[ir1]
  ans += p * ((i-il1)*(ir2-ir1) + (ir1-i)*(il1 -il2))
  before_idx[ir1] = il1
  next_idx[il1] = ir1


print (ans)

Submission status: Accepted

Solution code:
class BIT:
  
  def __init__(self, N):
    self.n = N
    self.tree = [0]*(self.n+1)
    
  def bsum(self, i):
    s = 0
    while i:
      s += self.tree[i]
      i -= i&(-i)
    return s
  
  def badd(self, i, x):
    while i<=self.n:
      self.tree[i] += x
      i += i&(-i)
  
  def bsearch(self, x):
    i = 0
    s = 0
    step = 1<<(self.n.bit_length()-1)
    while step:
      if i+step<=self.n and s+self.tree[i+step]<x:
        i += step
        s += self.tree[i]
      step >>= 1
    return i+1

      
N = int(input())
P = [0]+[int(c) for c in input().split()]

ntoi = [0]*(N+1)
for i in range(N+1):
  ntoi[P[i]] = i

bit = BIT(N)

ans = 0
for m in range(N, 0, -1):
  I = ntoi[m]
  L = bit.bsum(I)
  bit.badd(I,1)
  R = N-L-m
  a = bit.bsearch(L-1) if L>1 else 0
  b = bit.bsearch(L) if L>0 else 0
  c = bit.bsearch(L+2) if R>0 else N+1
  d = bit.bsearch(L+3) if R>1 else N+1
  coef = 0
  if b!=0:
    coef += (b-a)*(c-I)
  if c!=0:
    coef += (I-b)*(d-c)
  ans += m*coef

print(ans)

Submission status: Accepted

Solution code:
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
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
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 = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)

    def search(self, k):
        if k > self.total or k <= 0:
            return -1
        step = 1 << (self.size.bit_length() - 1)
        now_index = 0
        ret = 0
        while step:
            if now_index + step < self.size and ret + self.bit[now_index + step - 1] < k:
                ret += self.bit[now_index + step - 1]
                now_index += step
            step >>= 1
        # now_indexを伸ばしいって、sumがk以上に達する直前まで伸ばし続けるならreturnのところでnow_index - 1。
        # その場合、bit.sum(now_index - 1) <= k < bit.sum(now_index)
        # 達してすぐのindexであれば-1しない
        return now_index

n = I()
P = LI()
val_idx = {P[j]:j+1 for j in range(n)}
bit = BIT(n + 2)
bit.add(n + 1, 1)
bit.add(0, 1)
ans = 0
for k in range(n, 0, -1):
    idx = val_idx[k]
    m = bit.sum(idx)
    l1 = bit.search(m - 1)
    l2 = bit.search(m)
    r1 = bit.search(m + 1)
    r2 = bit.search(m + 2)
    if l1 >= 0:
        ans += (l2 - l1) * (r1 - idx) * k
    if r2 >= 0:
        ans += (idx - l2) * (r2 - r1) * k
    bit.add(idx, 1)

print(ans)

Submission status: Accepted

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

order = [None] * N
for i,p in enumerate(P):
    order[p-1] = i

bit = [0] * (N+2)
def bit_add(x,w):
    while x <= N+1:
        bit[x] += w
        x += (x & -x)
def bit_sum(x):
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

def bisect_right(k):
    def is_ok(i):
        if i < 1: return True
        if i > N+1: return False
        return bit_sum(i) <= k
    ok = 0
    ng = N+2
    while ng-ok > 1:
        m = (ok+ng) // 2
        if is_ok(m):
            ok = m
        else:
            ng = m
    return ok

ans = 0
for q,i in enumerate(reversed(order)):
    bit_add(i+2, 1)
    #print([bit_sum(i) for i in range(1,N+2)])
    k = bit_sum(i+2)
    a = bisect_right(k-3)
    b = bisect_right(k-2)
    c = bisect_right(k-1)
    d = bisect_right(k)
    e = bisect_right(k+1)
    ans += ((b-a)*(d-c) + (c-b)*(e-d)) * (N-q)
print(ans)

Submission status: Accepted

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

D = [0]*N

for i in range(N):
    D[P[i]-1] = i

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    #you can use this function when the BIT has only non-negative values.
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x

bit = BIT([0]*N)

def calc_num(x,l1,l2,h1,h2):
    A = (l1-l2)*(h1-x)
    B = (h2-h1)*(x-l1)
    return A+B

ans = 0

for i in range(N):
    j = N-i-1
    bit.add(D[j],1)
    s = bit.sum(D[j])
    if s==i+1:
        h1=h2=N
    elif s==i:
        h2=N
        h1 = bit.lower_bound(s+1)
    else:
        h1 = bit.lower_bound(s+1)
        h2 = bit.lower_bound(s+2)
    if s==1:
        l1=l2=-1
    elif s==2:
        l1 = bit.lower_bound(s-1)
        l2 = -1
    else:
        l1 = bit.lower_bound(s-1)
        l2 = bit.lower_bound(s-2)

    #print(D[j],l1,l2,h1,h2)
    #print(calc_num(D[j],l1,l2,h1,h2))
    ans += calc_num(D[j],l1,l2,h1,h2)*(j+1)

print(ans)