#P15808. [中国国家队2025年林芝集训]象形文字序列

    ID: 15019 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>数据结构分块动态规划算法基础数学CF3200

[中国国家队2025年林芝集训]象形文字序列

题目描述

一个研究团队正在研究象形文字序列的一些性质。他们将每个象形文字的复杂程度表示成一个正整数,并且没有两个象形文字被表示成相同的数。

对于一个长度为 nn、下标从 11 开始的序列 AA,定义如下概念:

  1. AA 被称为一个排列,当且仅当 1,2,…,n1,2,\ldots,n 在 AA 中分别恰好出现一次。
  2. 序列 BB 被称为 AA 的子序列,当且仅当 BB 可以通过删除 AA 中若干个元素得到,删除元素的数量可以为 00。
  3. AA 的区间 [l,r][l,r] 指序列 Al,Al+1,…,ArA_l,A_{l+1},\ldots,A_r。

研究人员想知道:对于给定排列 AA 的若干个区间 [li,ri][l_i,r_i],该区间内最长上升子序列的长度是多少。

输入格式

第一行包含两个正整数 n,qn,q,分别表示排列大小和询问个数。

第二行包含 nn 个正整数 aia_i,表示排列 AA。

接下来 qq 行,每行包含两个正整数 li,ril_i,r_i,表示一次查询的区间。

输出格式

输出 qq 行,每行输出一个正整数,表示对应区间的最长上升子序列长度。

数据范围

对于所有数据,保证:

  • 1≤n≤1051\le n\le 10^5;
  • 1≤q≤1061\le q\le 10^6;
  • 1≤ai≤n1\le a_i\le n;
  • AA 是一个排列。

子任务

子任务编号 分数 特殊限制
1 5 ri−li≤10r_i-l_i\le 10
2 25 n≤10000n\le 10000
3 30 li−1≤li, ri−1≤ril_{i-1}\le l_i,\ r_{i-1}\le r_i
4 aa 在所有长度为 nn 的排列中等概率选取
5 10 无特殊限制

样例

输入

5 5
1 5 2 4 3
1 5
2 4
3 3
1 4
2 5

输出

3
2
1
3
2