#1751. Perotation

    ID: 1751 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1091来源:qoj.ac数据:公开样例单调栈

Perotation

Perotation

题目描述

标题: Perotation - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

对于一个元素互不相同的序列 a1,a2,⋯,an,我们定义一次合法的操作如下:

  • 选取一个 i∈[2,n−1],满足 ai−1<ai<ai+1。
  • 将 ai+1 移动到 ai−1 之前。也就是说假设原序列中 i−1,i,i+1 位置的值分别为 ai−1,ai,ai+1,则新的序列中 i−1,i,i+1 位置的值分别为 ai+1,ai−1,ai。

比如,a=[1,2,3,4,5],如果在这一次操作中选取 i=3,序列将会变为 [1,4,2,3,5]。

我们定义一个序列是合法的,当且仅当它能够由一个单调上升的序列通过有限多次操作得到。

给定一个长度为 n 的排列 a1,a2,⋯,an,有 q 次修改,每次修改形如交换 ax 和 ay 的值。你需要在每次修改后,回答最小的正整数 k,满足 ak,ak+1,⋯,an 为一个合法的序列。不难发现,任意长度为 1 的序列均为合法序列,因而最小的正整数 k 一定存在,且唯一。

输入格式

第一行两个整数 n,q。

第二行一行 n 个整数,用空格隔开,依次表示 a1,a2,⋯,an。

接下来 q 行,每行两个整数 x,y,描述一次修改。

输出格式

输出 q 行,每行一个整数,表示答案。

样例数据

样例输入

7 5
6 7 2 1 5 3 4
3 1
3 1
7 5
1 6
6 5

样例输出

3
4
6
7
4

样例解释

在第三次操作后,序列变为 6 7 2 1 4 3 5。

对于长度为 1 的子序列,显然其合法,因而 a7 是一个合法的序列。

对于长度为 2 的子序列 3 5,由于其初始时候有序,显然其合法。因而 a6a7 是一个合法的序列。

对于长度为 3 的子序列 4 3 5,由于从初始状态只能转移到 3 4 5 和 5 3 4,显然其非法,因而 a5a6a7 是一个非法的序列。

类似的,我们总可以说明当 k=1,2,3,4 时,ak,ak+1,⋯,an 非法。

因此答案为 6。

子任务

  • Subtask 1(10%): 保证 n≤10
  • Subtask 2(20%): 保证 n≤100
  • Subtask 3(30%): 保证 n≤5000
  • Subtask 4(40%): 无特殊限制。

对于所有测试数据,保证 2≤n≤100000,1≤q≤100000。

对于每一次询问,满足 1≤x,y≤n,x≠y。

保证 ai 是一个 [1,n] 的排列。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

7 5
6 7 2 1 5 3 4
3 1
3 1
7 5
1 6
6 5
3
4
6
7
4