6E - Exposition - CodeForces Solution

import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_search(c1, c2):
    m = (c1 + c2 + 1) // 2
    while abs(c1 - c2) > 1:
        m = (c1 + c2 + 1) // 2
        if ok(m):
            c1 = m
        else:
            c2 = m
    m = min(m + 1, n)
    while not ok(m):
        m -= 1
    return m

def ok(m):
    if m > n:
        return False
    elif m <= 0:
        return True
    x, y = slide_min(n, m, h), slide_max(n, m, h)
    for i, j in zip(y, x):
        if i - j <= k:
            return True
    return False

def slide_min(n, k, a):
    ans, s = [], []
    j = 0
    for i in range(n):
        ai = a[i]
        while len(s) ^ j and a[s[-1]] >= ai:
            s.pop()
        s.append(i)
        while len(s) ^ j and s[j] + k <= i:
            j += 1
        if i + 1 >= k:
            ans.append(a[s[j]])
    return ans

def slide_max(n, k, a):
    ans, s = [], []
    j = 0
    for i in range(n):
        ai = a[i]
        while len(s) ^ j and a[s[-1]] <= ai:
            s.pop()
        s.append(i)
        while len(s) ^ j and s[j] + k <= i:
            j += 1
        if i + 1 >= k:
            ans.append(a[s[j]])
    return ans

n, k = map(int, input().split())
h = list(map(int, input().split()))
a = binary_search(0, n + 1)
ans = []
x, y = slide_min(n, a, h), slide_max(n, a, h)
for i in range(n - a + 1):
    if y[i] - x[i] <= k:
        ans.append(" ".join(map(str, (i + 1, i + a))))
b = len(ans)
print(a, b)
sys.stdout.write("\n".join(ans))