fun main() = repeat(readln().toInt()) {
    val (n, q) = readln().split(' ').map { it.toInt() }
    val a = readln().split(' ').map { it.toInt() - 1 }.toIntArray()
    val b = log2(n) + 1

    val level = IntArray(n + 1) { n }
    val length = List(b) { IntArray(n + 1) }

    val lis = IntArray(n)
    fun go(l: Int, r: Int, lvl: Int) {
        if (l >= r) return

        val m = (l + r) / 2
        level[m] = lvl

        var curLength = 0
        for (i in m until r) {
            val idx = lowerBound(lis, curLength, a[i])
            if (idx == curLength) curLength++
            lis[idx] = a[i]
            length[lvl][i + 1] = curLength
        }

        curLength = 0
        for (i in (l until m).reversed()) {
            val idx = lowerBound(lis, curLength, n - a[i])
            if (idx == curLength) curLength++
            lis[idx] = n - a[i]
            length[lvl][i] = curLength
        }

        go(l, m - 1, lvl + 1)
        go(m + 1, r, lvl + 1)
    }
    go(0, n, 0)

    val levels = SegmentTree(n + 1, n, { x, y -> if (level[x] < level[y]) x else y }, { i -> i })
    val ans = IntArray(q)
    repeat(q) {
        val (l, r) = readln().split(' ').map { it.toInt() }.let { (l, r) -> l - 1 to r }
        val m = levels.get(l, r + 1)
        val lvl = level[m]
        val left = length[lvl][l]
        val right = length[lvl][r]
        val low = maxOf(left, right)
        val high = left + right
        ans[it] = if (left == 1 && right == 1) {
            if (a[m - 1] < a[m]) 2 else 1
        } else {
            (low + high) / 2
        }
    }
    println(ans.joinToString("\n"))
}

fun lowerBound(numbers: IntArray, length: Int, x: Int): Int {
    var low = -1
    var high = length
    while (high - low > 1) {
        val med = (low + high) / 2
        if (numbers[med] < x) low = med else high = med
    }
    return high
}

fun log2(x: Int) = 31 - x.countLeadingZeroBits()

class SegmentTree(sz: Int, val z: Int, val unite: (Int, Int) -> Int, init: (Int) -> Int = { z }) {
    val h = log2(sz) + 1
    val n: Int = 1 shl h
    val data: IntArray

    init {
        data = IntArray(2 * n) { z }
        for (i in 0 until sz) data[n + i] = init(i)
        for (i in n - 1 downTo 1) data[i] = unite(data[2 * i], data[2 * i + 1])
    }

    fun get(ql: Int, qr: Int): Int {
        var l = ql + n
        var r = qr + n
        var ans = z
        while (l < r) {
            if (l % 2 == 1) ans = unite(ans, data[l++])
            if (r % 2 == 1) ans = unite(ans, data[--r])
            l /= 2
            r /= 2
        }
        return ans
    }

    fun set(qi: Int, x: Int) {
        var i = qi + n
        data[i] = x
        while (i > 1) {
            i /= 2
            data[i] = unite(data[2 * i], data[2 * i + 1])
        }
    }
}
