Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.TreeSet
import java.util.BitSet
import java.util.HashMap
import kotlin.math.max

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine().toInt()
    val potentialCustomers = ArrayList<Pair<Pair<Long, Long>, Int>>(n)
    var potentialCustomerCount = 0
    for (i in 0 until n) {
        val parts = reader.readLine().split(" ")
        val arrival = parts[0].toLong()
        val departure = parts[1].toLong()
        if (departure - arrival >= 5) {
             potentialCustomers.add(Pair(Pair(arrival, departure), i))
             potentialCustomerCount++
        }
    }

    if (potentialCustomerCount == 0) {
        writer.write("0 1 6\\n")
        writer.flush(); reader.close(); writer.close()
        return
    }

    val candidateTimesSet = TreeSet<Long>()
    for ((times, _) in potentialCustomers) {
        candidateTimesSet.add(times.first)
        candidateTimesSet.add(times.second - 5)
    }

    val sortedTimes = candidateTimesSet.toTypedArray()
    val C = sortedTimes.size

    if (C == 0) {
        writer.write("0 1 6\\n")
         writer.flush(); reader.close(); writer.close()
        return
    }

    // --- Precomputation using Arrays ---
    // Map times to indices 0..C-1 for array access
    val timeToIndex = HashMap<Long, Int>(C)
    sortedTimes.forEachIndexed { index, time -> timeToIndex[time] = index }

    // Precompute audiences as Array<BitSet>
    val audienceArray = Array(C) { BitSet(potentialCustomerCount) }
    for (i in 0 until C) {
        val t = sortedTimes[i]
        // Reuse BitSet creation logic from previous attempts
        for (idx in 0 until potentialCustomerCount) {
             val arrival = potentialCustomers[idx].first.first
             val departure = potentialCustomers[idx].first.second
             if (arrival <= t && departure >= t + 5) {
                 audienceArray[i].set(idx)
             }
        }
    }

    // Precompute cardinalities (audience sizes)
    val audienceSizeArray = IntArray(C) { audienceArray[it].cardinality() }
    // --- End Precomputation ---

    var maxListeners = 0
    var bestT1Idx = 0
    var bestT2Idx = -1 // Use -1 to indicate no pair found yet / single is best

    // Baseline with single best time
    for (i in 0 until C) {
        if (audienceSizeArray[i] > maxListeners) {
            maxListeners = audienceSizeArray[i]
            bestT1Idx = i
            bestT2Idx = -1 // Mark as single best
        }
    }

    // Temporary BitSet for intersection calculation, created outside the inner loop
    val tempIntersection = BitSet(potentialCustomerCount)

    // Iterate pairs using indices
    for (i in 0 until C) {
        val t1 = sortedTimes[i]
        val audience1 = audienceArray[i]
        val size1 = audienceSizeArray[i]
        val minT2Time = t1 + 5

        // Iterate potential t2 indices
        for (j in i until C) {
            val t2 = sortedTimes[j]
            if (t2 >= minT2Time) {
                val audience2 = audienceArray[j]
                val size2 = audienceSizeArray[j]

                // Calculate intersection size: intersection = A1 & A2
                // Reuse tempIntersection BitSet
                tempIntersection.clear()          // Clear previous bits
                tempIntersection.or(audience1)   // Copy audience1 bits
                tempIntersection.and(audience2)  // Intersect with audience2
                val intersectionSize = tempIntersection.cardinality()

                val currentListeners = size1 + size2 - intersectionSize

                if (currentListeners > maxListeners) {
                    maxListeners = currentListeners
                    bestT1Idx = i
                    bestT2Idx = j // Mark as pair best
                }
            }
        }
    }

    // Retrieve actual times from indices
    val finalBestT1 = sortedTimes[bestT1Idx]
    // If bestT2Idx is -1, it means the single broadcast was optimal.
    // Otherwise, use the time corresponding to bestT2Idx.
    val finalBestT2 = if (bestT2Idx == -1) {
        finalBestT1 + 5 // Use default offset if single was best
    } else {
        sortedTimes[bestT2Idx] // Use the actual partner time if pair was best
    }

    writer.write("$maxListeners $finalBestT1 $finalBestT2\\n")

    reader.close()
    writer.flush()
    writer.close()
}