实习面试题-大厂算法真题面试题

1.百度2023秋招-交换一次获得长度为k的排列

题目描述

小红有一个长度为n的排列，她可以选择两个位置，然后交换两个位置的数。

她想知道能否通过最多一次交换，使得存在一个连续子段，是长度为k的排列。

排列是指一个长度为len的整数数组，数组中包含1到len的每个数，且每个数只出现一次。

输入描述

第一行两个整数n, k，表示排列长度和连续子段长度。

第二行n个整数a1, a2, ..., an，表示排列。

1 <= k <= n <= 10^5

输出描述

如果能够通过最多一次交换，存在一个连续子段是排列，输出YES，并输出交换的位置：先输出一个整数x (0 <= x <= 1)，然后输出x行，每行两个整数u, v，表示交换位置u, v (u < v)

否则输出NO。

示例

输入