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

import sys
sys.setrecursionlimit(1000000)

n = int(input())
lists = list(map(int,input().split()))
res = []
def func(i, sum):
    if i == n-1:
        return sum
    if lists[i] < lists[i+1]:
        return sum
    return func(i+1, sum+1)

for j in range(n):
    res.append(func(j, 0))
print(max(res))



### FIXED CODE ###

import sys
sys.setrecursionlimit(100000) 

n = int(input())
high = list(map(int,input().split()))
lists = []

def func(i,t):
    if i == n - 1:
        lists.append(t)
        return
    if high[i] < high[i+1]:
        lists.append(t)
        func(i+1,0)
    else:
        t += 1
        func(i+1,t)

func(0,0)
print(max(lists))
### BUGGY CODE ###

N = int(input())
binary = [0]*60
for inp in input().split():
    inp = bin(int(inp))[2:][::-1]
    for j, _inp in enumerate(inp):
        binary[j] += int(_inp)
    
ret = 0
pow2 = 1
for elem in binary:
    if elem == 0 or elem == N:
        pass
    else: 
        mn = elem * (N - elem) % (10**9 + 7)
        ret += pow2 * mn % (10**9 + 7)
    pow2 = pow2 * 2 % (10**9 + 7)
print(ret % (10**9 + 7))

### FIXED CODE ###

N = int(input())
binary = [0]*60
for inp in input().split():
    inp = bin(int(inp))[2:][::-1]
    for j, _inp in enumerate(inp):
        if _inp == '1':
            binary[j] += 1
    
ret = 0
pow2 = 1
for elem in binary:
    if elem == 0 or elem == N:
        pass
    else: 
        mn = elem * (N - elem) % (10**9 + 7)
        ret += pow2 * mn 
        ret = ret % (10**9 + 7)
    pow2 = pow2 * 2 % (10**9 + 7)
print(ret)
### BUGGY CODE ###

import numpy as np

n = int(input())
A = list(map(int,input().split()))
S = sum(A)
ans = []
for i in range(1,n+1):
    aaa = A[i:]+A[:i]
    # print(aaa[:-1:2])
    x = S-(sum(aaa[:-1:2]))*2
    ans.append(x)

[print(a) for a in ans]

### FIXED CODE ###

import numpy as np

n = int(input())
A = list(map(int,input().split()))
S = sum(A)

x = S-sum(A[1:-1:2])*2
print(x)
for a in A[:-1]:
    x = (a-x//2)*2
    print(x)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

def gcd(x, y):
    x, y = max(x, y), min(x, y)
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

lcm = 1
for i in range(len(A)):
    lcm = A[i] * lcm // gcd(A[i], lcm)

B = 0
for i in range(len(A)):
    B += lcm // A[i]

print(B % mod)

### FIXED CODE ###

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
  while b:a,b=b,a%b
  return a
def lcm(a,b):return a*b//gcd(a,b)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)
### BUGGY CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = [(i-1) % m+1 for i in d]
        print(n-1-(x % m+sum(d2)*((n-2)//k)+sum(d2[:(n-2) % k+1]))//m)


main()


### FIXED CODE ###

def main():
    k, q = map(int, input().split())
    d = list(map(int, input().split()))
    nxm = [list(map(int, input().split())) for _ in [0]*q]
    for n, x, m in nxm:
        d2 = sum([(i-1) % m+1 for i in d[:(n-2) % k+1]])
        d3 = sum([(i-1) % m+1 for i in d[(n-2) % k+1:]])
        print(n-1-(x % m+(d2+d3)*((n-2)//k)+d2)//m)


main()
### BUGGY CODE ###

from operator import mul
from functools import reduce

N,M=map(int,input().split())
P=10**9+7
ans=1

def Pdeco(m):
    ret=[]
    for i in range(2,M):
        if m<=i:
            if m!=1: ret.append(int(m))
            break
        while m%i==0:
            m=m//i
            ret.append(i)
    return ret


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

L=Pdeco(M)
nums=set(L)

for n in nums:
    p=L.count(n)
    ans=(ans*cmb(N+p-1,N-1))%P

print(ans)

### FIXED CODE ###

from operator import mul
from functools import reduce

N,M=map(int,input().split())
P=10**9+7
ans=1

def Pdeco(m):
    ret=[]
    for i in range(2,int((M)**(0.5))+100):
        if m<=i:
            if m!=1: ret.append(int(m))
            break
        elif i>int((M)**(0.5)+50):
            ret.append(m)
            break

        while m%i==0:
            m=m//i
            ret.append(i)
    return ret


def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

L=Pdeco(M)
nums=set(L)

for n in nums:
    p=L.count(n)
    ans=(ans*cmb(N+p-1,N-1))%P

print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = list(input())
n = len(s)
MOD = 10**9 + 7

al = [0]*(n+1)
bl = [0]*(n+1)
cl = [0]*(n+1)
ql = [0]*(n+1)
for i in range(n):
    if s[i]=="A":
        al[i+1] += 1
    elif s[i]=="B":
        bl[i+1] += 1
    elif s[i]=="C":
        cl[i+1] += 1
    else:
        ql[i+1] += 1

    al[i+1] += al[i]
    bl[i+1] += bl[i]
    cl[i+1] += cl[i]
    ql[i+1] += ql[i]

res = 0
for i in range(n):
    if s[i]=="A" or s[i]=="C":
        continue

    res += (al[i]-al[0])*(cl[n]-cl[i+1])*3**(ql[i]-ql[0] + ql[n]-ql[i+1])
    res += (al[i]-al[0])*(ql[n]-ql[i+1])*3**(ql[i]-ql[0] + ql[n]-ql[i+1]-1)
    res += (ql[i]-ql[0])*(cl[n]-cl[i+1])*3**(ql[i]-ql[0]-1 + ql[n]-ql[i+1])
    res += (ql[i]-ql[0])*(ql[n]-ql[i+1])*3**(ql[i]-ql[0]-1 + ql[n]-ql[i+1]-1)
    res %= MOD
print(int(res))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import unittest

MOD = 10**9 + 7

def func(s):
    abc = "ABC"
    n = len(s)
    dp =[[0 for _ in range(3+1)] for _ in range(n+1)]
    dp[n][3] = 1

    for i in range(n-1,-1,-1):
        for j in range(3,-1,-1):
            if j==3:
                if s[i]=="?":
                    dp[i][j] = (dp[i+1][j]*3)%MOD
                else:
                    dp[i][j] = dp[i+1][j]
            else:
                m1 = 3 if s[i]=="?" else 1
                m2 = 1 if s[i]=="?" or s[i]==abc[j] else 0
                dp[i][j] = ((m1*dp[i+1][j])%MOD + (m2*dp[i+1][j+1])%MOD)%MOD
    return dp[0][0]

class Test(unittest.TestCase):
    def test(self):
        self.assertEqual(func("A??C"), 8)
        self.assertEqual(func("ABCBC"), 3)
        self.assertEqual(func("????C?????B??????A???????"), 979596887
)

if __name__ == '__main__':
    print(func(input()))
### BUGGY CODE ###

import heapq

N, M =map(int, input().split())
p = []

for _ in range(M):
    A, B= map(int, input().split())
    n = B - A
    m = {i for i in range(A, B)}
    heapq.heappush(p, (n, m))

n = 0
sets = []
for _ in range(M):
    n, q = heapq.heappop(p)
    for m, s in sets:
        if len(s - q) == 0:
            break
    else:
        heapq.heappush(sets, (max(q), q))
    
count = 0
minnum = -1
for _ in range(len(sets)):
    n, q = heapq.heappop(sets)
    if minnum in q:
        continue
    minnum = n
    count += 1

print(count)

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    Q = [read_list() for _ in range(M)]
    Q.sort()

    res = 0
    end = 10 ** 6
    for q in Q:
        if q[0] >= end:
            res += 1
            end = q[1]
        else:
            end = min(end, q[1])
    
    res += 1
    print(res)


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

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

for i in reversed(range(max1)):
  rest1 = y-i*1000
  max2 = int((rest1)/5000) + 1
  for ii in reversed(range(max2)):
    rest2 = y-i*1000-ii*5000
    mod = rest2%10000
    iii = int(rest2/10000)
    tot = i+ii+iii
    if(mod == 0 and tot == n):
      print(iii, ii, i)
      sys.exit()

print(-1,-1,-1)

### FIXED CODE ###

import math
import sys
import numpy as np
import collections

#n, a, b= map(int, input().split())
n, y  = map(int, input().split())
#s = list(str(input()))
#n = int(input())

max1 = int(y/1000) + 1

for i in range(max1):
  rest = y-i*9000-n*1000
  mod = rest%4000
  ii  = int((rest)/4000)
  iii = n-i-ii
  if(mod == 0 and iii>=0 and ii>=0):
    print(i, ii, iii)
    sys.exit()
    
print(-1,-1,-1)
### BUGGY CODE ###

import fractions

def GCD(a,b,c):
    return fractions.gcd(fractions.gcd(a,b),c)

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += GCD(i,j,k)
print(ans)

### FIXED CODE ###

import math

def GCD(a,b,c):
    return math.gcd(math.gcd(a,b),c)

k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans += GCD(i,j,k)
print(ans)
### BUGGY CODE ###

N = int(input())
a = []
elements = set()
for i in input().split():
    a.append(int(i))
    elements.add(int(i))
max_count = 0
for X in elements:
    count1 = 0
    count2 = 0
    count3 = 0
    for num in a:
        if X-1 <= num <= X+1:
            count1 += 1
        if X <= num <= X+2:
            count2 += 1
        if X-2 <= num <= X:
            count3 += 1
    max_count = max(max_count, count1, count2, count3)
print(max_count)

### FIXED CODE ###

def dic_counter(dic, num):
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

N = int(input())
dic = {}
for i in input().split():
    dic_counter(dic, int(i)-1)
    dic_counter(dic, int(i))
    dic_counter(dic, int(i)+1)
for _, value in sorted(dic.items(), key=lambda x: -x[1]):
    print(value)
    break
### BUGGY CODE ###

from math import gcd

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

npcf = False
for i in range(N - 1):
    for j in range(i + 1, N):
        if gcd(A[i], A[j]) != 1:
            npcf = True
            break
    if npcf:
        break

if not npcf:
    print('pairwise coprime')
    exit()

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

from math import gcd

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

prime = list(range(max(A) + 1))

for i in range(2, len(prime)):
    if prime[i] != i:
        continue
    for j in range(i, len(prime), i):
        if prime[j] != j:
            continue
        prime[j] = i

used = set()
pc = True
for a in A:
    used_this = set()
    while a != 1:
        div = prime[a]
        if div in used:
            pc = False
            break
        used_this.add(div)
        a //= div
    used.update(used_this)

if pc:
    print('pairwise coprime')
    exit()

buf = A[0]
for a in A[1:]:
    buf = gcd(buf, a)
if buf == 1:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

import numpy as np
from numba import njit

N,K = map(int, input().split())

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(K):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")


### FIXED CODE ###

import numpy as np
from numba import njit

N,K = map(int, input().split())

A_list = np.array([0]+list(map(int, input().split())))

@njit
def update(A_list):

  for j in range(min(K,46)):
    new_A=np.zeros(N+2,dtype=np.int64)
    for i in range(1,N+1):
      #print(new_A)
      mi=i-A_list[i]
      ma=i+A_list[i]
      if mi<0:
        mi=0
      if ma>N:
        ma=N
      #new_A[mi:ma+1]+=1
      new_A[mi]+=1
      new_A[ma+1]-=1

    A_list=np.cumsum(new_A)
    #if sum(A_list[1:N+1])==N*N:
    #  return(A_list)    
    #  break
      
  return(A_list)

A_list=update(A_list)
for i in range(1,N+1):
  print(A_list[i],end=" ")
### BUGGY CODE ###

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


import bisect
A.sort()

A = [-1] + A

for i in range(M):
    b, c = map(int, input().split())
    idx = bisect.bisect_left(A, c)
    #print(A[:idx], A[idx:])
    A = A[:idx] + [c] * b + A[idx:]
    A = A[-N:]
    #print(A)
    
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###


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

A.sort()

CB = []
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
    
CB.sort(reverse=True)

idx = 0
c = 0
for i in range(N):
    if A[i] < CB[idx][0]:
        A[i] = CB[idx][0]
        c += 1
    if CB[idx][1] <= c:
        idx += 1
        c = 0
    if idx >= M:
        break
    #print(A)
        
print(sum(A))
### BUGGY CODE ###

import heapq

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

change = []
for m in range(M):
    B, C = map(int, input().split())
    change.append((B, C))
change.sort(key=lambda x: -x[1])

change2 = []
for c in change:
    change2.extend([c[1]] * c[0])


heapq.heapify(A)

for c in change2:
    x = heapq.heappop(A)
    if x >= c:
        # 先頭すでに十分大きい場合は抜ける
        heapq.heappush(A, x)
        break
    else:
        x = max(x, c)
        heapq.heappush(A, x)

print(sum(A))


### FIXED CODE ###

import heapq

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

change = []
for m in range(M):
    B, C = map(int, input().split())
    change.append((B, C))
change.sort(key=lambda x: -x[1])

change2 = []
for c in change:
    change2.extend([c[1]] * c[0])
    if len(change2) >= N:
        change2 = change2[:N]
        break


heapq.heapify(A)

for c in change2:
    x = heapq.heappop(A)
    if x >= c:
        # 先頭すでに十分大きい場合は抜ける
        heapq.heappush(A, x)
        break
    else:
        x = max(x, c)
        heapq.heappush(A, x)

print(sum(A))
### BUGGY CODE ###

N=int(input())
H=list(map(int,input().split()))
ans=0
for i in range(N-1):
  tmp=0
  for j in range(i,N-1):
    if H[j] >= H[j+1]:
      tmp += 1
    else:
      break
  ans = max(ans,tmp)
print(ans)

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
ans=0
i = 0

while i < N-1:
  tmp=0
  for j in range(i,N-1):
    if H[j] >= H[j+1]:
      tmp += 1
    else:
      break
  ans = max(ans,tmp)
  i = i + tmp +1
print(ans)
### BUGGY CODE ###

def bisect_right_reverse(a, x):
    if a[0] < x:
        return 0
    if x <= a[-1]:
        return len(a)
    ok = len(a) - 1
    ng = 0
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] < x:
            ok = mid
        else:
            ng = mid
    return ok

#import bisect
X, Y, A, B, C = map(int, input().split())
red = [int(x) for x in input().split()]
gre = [int(x) for x in input().split()]
non = [int(x) for x in input().split()]
red.sort(reverse=True)
gre.sort(reverse=True)
non.sort()
ans = red[:X] + gre[:Y]
ans.sort(reverse=True)
while non[-1] > ans[-1]:
    c = non[-1]
    index = bisect_right_reverse(ans, c)
    ans.insert(index, c)
    non.pop(-1)
    ans.pop(-1)
    if non == []:
        break
print(sum(ans))

### FIXED CODE ###

X, Y, R, G, N = map(int, input().split())
r = [int(x) for x in input().split()]
g = [int(x) for x in input().split()]
n = [int(x) for x in input().split()]
r = sorted(r)[R-X:]
g = sorted(g)[G-Y:]
n = sorted(n, reverse=True)

nr = 0; ng = 0; nn = 0
for i in range(N):
    if n[nn] <= min(r[nr], g[ng]):
        break
    if r[nr] < g[ng]:
        r[nr] = n[nn]
        nr += 1
        if nr == X:
            nr = X-1
    else:
        g[ng] = n[nn]
        ng += 1
        if ng == Y:
            ng = Y-1
    nn += 1

print(sum(r) + sum(g))
### BUGGY CODE ###

n,m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
dp[0],ans = 1,1
dp[1] = (0 if 1 in a else 1)
for i in range(2,n+1):
    if i in a:continue
    dp[i] = dp[i-1]+dp[i-2]
print(dp[n]%1000000007)

### FIXED CODE ###

n,m = map(int, input().split())
a = set([int(input()) for i in range(m)])
memo = [0]*(n+1)

memo[0] = 1
if 1 in a:
    memo[1] = 0
else:
    memo[1] = 1
for i in range(2,n+1):
    if i in a:
        continue
    memo[i] = (memo[i-1] + memo[i-2])%1000000007

print(memo[n])
### BUGGY CODE ###

s = input()
s_len = len(s)

to_l = [0] * s_len
to_r = [0] * s_len
ans = [0] * s_len
cnt = 0
for i, c in enumerate(s):
    if c == 'R':
        cnt = 0
    else:
        cnt += 1
    to_r[i] = cnt

cnt = 0
for i,c in enumerate(reversed(s)):
    if c == 'L':
        cnt = 0
    else:
        cnt += 1
    to_l[s_len-i-1] = cnt

for i in range(s_len):
    c = s[i]
    if c == 'R':
        d = to_l[i]
    else:
        d = to_r[i]

    if d % 2 == 0:
        to_d = d
    else:
        to_d = d - 1

    if c == 'R':
        to_i = i + to_d
    else:
        to_i = i - to_d
    
    if to_i < 0 or s_len <= to_i:
        pass
    else:
        ans[to_i] += 1

ans_s = str(ans[0])
for cnt in ans[1:]:
    ans_s += (" " + str(cnt))
print(ans_s)


### FIXED CODE ###

s = input()
s_len = len(s)

to_l = [0] * s_len
to_r = [0] * s_len
ans = [0] * s_len
cnt = 0
for i, c in enumerate(s):
    if c == 'R':
        cnt = 0
    else:
        cnt += 1
    to_r[i] = cnt

cnt = 0
for i,c in enumerate(reversed(s)):
    if c == 'L':
        cnt = 0
    else:
        cnt += 1
    to_l[s_len-i-1] = cnt

for i in range(s_len):
    c = s[i]
    if c == 'R':
        d = to_l[i]
    else:
        d = to_r[i]

    if d % 2 == 0:
        to_d = d
    else:
        to_d = d - 1

    if c == 'R':
        to_i = i + to_d
    else:
        to_i = i - to_d
    
    if to_i < 0 or s_len <= to_i:
        pass
    else:
        ans[to_i] += 1

#ans_s = str(ans[0])
#for cnt in ans[1:]:
#    ans_s += (" " + str(cnt))
#print(ans_s)
for i in ans:
    print(i)
### BUGGY CODE ###

mod = 10 ** 9 + 7
h, w, k = map(int, input().split())

def dfs(i, j):
    cnt = 0
    if i == h + 1:
        if j == k:
            return 1
        else:
            return 0
    if j == 1:
        cnt += dfs(i + 1, j) 
        cnt += dfs(i + 1, j + 1)
    elif j == w:
        cnt +=  dfs(i + 1, j) 
        cnt += dfs(i + 1, j - 1)
    else:
        cnt += dfs(i + 1, j)
        cnt += dfs(i + 1, j + 1) 
        cnt += dfs(i + 1, j - 1)        
    return cnt

if w == 1:
    print(1)
else:
    print(dfs(0, 0) % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
H, W, K = map(int, input().split())
dp = [[0] * W for i in range(H + 1)]

dp[0][0] = 1
for i in range(H):
    for j in range(W):
        for k in range(1 << (W - 1)):
            ok = True
            if '11' in bin(k):
                ok = False
            if ok:
                if j >= 1 and ((k >> (j - 1)) & 1):
                    dp[i + 1][j - 1] += dp[i][j]
                    dp[i + 1][j - 1] %= mod
                    #print(1, i, bin(k), j, dp)
                    
                elif j <= W -2 and ((k >> j) & 1):
                    dp[i + 1][j + 1] += dp[i][j]
                    dp[i + 1][j + 1] %= mod
                    #print(2, i, bin(k), j, dp)
                    
                else:
                    dp[i + 1][j] += dp[i][j]
                    dp[i + 1][j] %= mod
                    #print(3, i, bin(k), j, dp)
            
print(dp[H][K - 1])
### BUGGY CODE ###

import math
def f(x,y,z):
    # x,y,z = A,x,B
    return math.floor(x*y/z) - x*math.floor(y/z)
a,b,n = map(int,input().split())
if n<b:
    print(math.floor(a*n/b))
else:
    k = n//b
    ret = f(a, b-1, b)
    for kk in range(1, k+1):
        ret = max(ret, f(a,b*kk-1,b))
    print(ret)

### FIXED CODE ###

import math
def f(x,y,z):
    # x,y,z = A,x,B
    return math.floor(x*y/z) - x*math.floor(y/z)
a,b,n = map(int,input().split())
if n<b:
    print(math.floor(a*n/b))
else:
    print(f(a, b-1, b))
### BUGGY CODE ###

def main():
    
    n = int(input())
    a = list(map(int,input().split()))
    for i in range(n):
        for j in range(i+1,n):
            if a[i]==a[j]:
                print("NO")
                return
    print("YES")

main()

### FIXED CODE ###

def main():
    
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    for i in range(n-1):
        for j in range(i,i+1):
            if a[i]==a[i+1]:
                print("NO")
                return
    print("YES")

main()
### BUGGY CODE ###

import heapq
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    es[a].append((b,c))
    es[b].append((a,c))

INF = float('inf')
dist = [[INF]*N for i in range(N)]
for i in range(N):
    dist[i][i] = 0

for i in range(N):
    hq = [i]
    heapq.heapify(hq)
    while hq:
        v = heapq.heappop(hq)
        k,j = divmod(v,N)
        k,l = divmod(k,L)
        for to,c in es[j]:
            if l+c > L:
                newcost = (k+1)*L + c
            else:
                newcost = k*L + l + c
            if newcost < dist[i][to]:
                dist[i][to] = newcost
                heapq.heappush(hq, newcost*N + to)

for s,t in ST:
    s,t = s-1,t-1
    if dist[s][t] == INF:
        print(-1)
    else:
        print((dist[s][t]-1)//L)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M,L = map(int,input().split())
ABC = [tuple(map(int,input().split())) for i in range(M)]
Q = int(input())
ST = [tuple(map(int,input().split())) for i in range(Q)]

INF = float('inf')
dist1 = [[INF]*N for i in range(N)]
dist2 = [[INF]*N for i in range(N)]
for a,b,c in ABC:
    if c > L: continue
    a,b = a-1,b-1
    dist1[a][b] = dist1[b][a] = c
for i in range(N):
    dist1[i][i] = 0
    dist2[i][i] = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist1[i][k] + dist1[k][j]
            if dist1[i][j] <= d: continue
            dist1[i][j] = d
for i in range(N):
    for j in range(N):
        if i==j: continue
        if dist1[i][j] <= L:
            dist2[i][j] = 1
for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist2[i][k] + dist2[k][j]
            if dist2[i][j] <= d: continue
            dist2[i][j] = d
ans = []
for s,t in ST:
    d = dist2[s-1][t-1]
    if d == INF:
        ans.append(-1)
    else:
        ans.append(d-1)
print(*ans, sep='\n')
### BUGGY CODE ###

N = int(input())
An_input = input().split()
An = [int(s) for s in An_input]

#print(An)
A = An[0] + An[1]
#print(A)

cnt = 0
M = 10**9 + 7

for i in range(0, N-1):
    #print(i)
    for l in range(1, N-i):
        cnt += An[i] * An[i+l]
        #print(An[i], An[i+l])
        #print(cnt)

ans = cnt % M
print(ans)

### FIXED CODE ###

N = int(input())
An_input = input().split()
An = [int(s) for s in An_input]

cnt = 0
k = 0
M = 10**9 + 7

for i in range(0, N-1):
    k += An[i]
    cnt += k * An[i+1]

ans = cnt % M
print(ans)
### BUGGY CODE ###

import numpy as np
N, M, Q = map(int, input().split())
dp = np.zeros((N,N), dtype=np.int32)
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  dp[i] = np.flipud(np.cumsum(np.flipud(dp[i])))
for i in range(N-1):
  dp[i+1] += dp[i]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])

### FIXED CODE ###

N, M, Q = map(int, input().split())
dp = [[0]*N for i in range(N)]
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  for j in range(N-1, 0, -1):
    dp[i][j-1] += dp[i][j]
for j in range(N):
  for i in range(N-1):
    dp[i+1][j] += dp[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])