human
Write me a the Python program you requested given the following:
Consider a sequence of digits of length 2^k [a_1, a_2, …, a_{2^k}]. We perform the following operation with it: replace pairs (a_{2i+1}, a_{2i+2}) with (a_{2i+1} + a_{2i+2})mod 10 for 0≤ i<2^{k-1}. For every i where a_{2i+1} + a_{2i+2}≥ 10 we get a candy! As a result, we will get a sequence of length 2^{k-1}.

Less formally, we partition sequence of length 2^k into 2^{k-1} pairs, each consisting of 2 numbers: the first pair consists of the first and second numbers, the second of the third and fourth …, the last pair consists of the (2^k-1)-th and (2^k)-th numbers. For every pair such that sum of numbers in it is at least 10, we get a candy. After that, we replace every pair of numbers with a remainder of the division of their sum by 10 (and don't change the order of the numbers).

Perform this operation with a resulting array until it becomes of length 1. Let f([a_1, a_2, …, a_{2^k}]) denote the number of candies we get in this process. 

For example: if the starting sequence is [8, 7, 3, 1, 7, 0, 9, 4] then:

After the first operation the sequence becomes [(8 + 7)mod 10, (3 + 1)mod 10, (7 + 0)mod 10, (9 + 4)mod 10] = [5, 4, 7, 3], and we get 2 candies as 8 + 7 ≥ 10 and 9 + 4 ≥ 10.

After the second operation the sequence becomes [(5 + 4)mod 10, (7 + 3)mod 10] = [9, 0], and we get one more candy as 7 + 3 ≥ 10. 

After the final operation sequence becomes [(9 + 0) mod 10] = [9]. 

Therefore, f([8, 7, 3, 1, 7, 0, 9, 4]) = 3 as we got 3 candies in total.

You are given a sequence of digits of length n s_1, s_2, … s_n. You have to answer q queries of the form (l_i, r_i), where for i-th query you have to output f([s_{l_i}, s_{l_i+1}, …, s_{r_i}]). It is guaranteed that r_i-l_i+1 is of form 2^k for some nonnegative integer k.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the length of the sequence.

The second line contains n digits s_1, s_2, …, s_n (0 ≤ s_i ≤ 9).

The third line contains a single integer q (1 ≤ q ≤ 10^5) — the number of queries.

Each of the next q lines contains two integers...
impor
assistant
#Here is the Python program you requested.
t sys

# def recur(pre,p,pos,maxx,temp):
#     if pos == len(pre):
#         maxx[0] = max(maxx[0],temp)
#         return
    
#     for i in range(0,p+1):
#         if i < len(pre[pos]) :
#             temp = temp + pre[pos][i]
#             recur(pre,p-i,pos+1,maxx,temp)
#             temp = temp - pre[pos][i]

RI = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

# for _ in range(int(ri())):
def query(seg,ss,se,qs,qe,pos):
    if qs <= ss and qe >= se:
        return seg[pos]
    if qs > se or qe < ss:
        return [0,0]
    mid= (ss+se)//2
    left = query(seg,ss,mid,qs,qe,2*pos+1)
    right = query(seg,mid+1,se,qs,qe,2*pos+2)
    # print(left,right)
    return [(left[0]+right[0])%10,left[1]+right[1] + (1 if (left[0]+right[0]) >= 10 else 0)]

def build(seg,pos,a,s,e):
    if s == e:
        seg[pos][0] = a[s]
        seg[pos][1] = 0
        return 
    mid= (s+e)//2
    build(seg,2*pos+1,a,s,mid)
    build(seg,2*pos+2,a,mid+1,e)
    seg[pos][1] = seg[2*pos+1][1] + seg[2*pos+2][1]
    num1 = seg[2*pos+1][0]
    num2 = seg[2*pos+2][0]
    if (num1+num2)>=10:
        seg[pos][1]+=1
    seg[pos][0]  = (num1+num2)%10

n = int(ri())
a = RI()
seg = [[0,0] for i in range(0,4*n+1)]

build(seg,0,a,0,n-1)
# print(seg)
q = int(ri())
for _ in range(q):
    l,r  = RI()
    l-=1
    r-=1
    res = query(seg,0,n-1,l,r,0)
    print(res[1])