小团从某不知名论坛上突然得到了一个测试默契度的游戏，想和小美玩一次来检验两人的默契程度。游戏规则十分简单，首先有给出一个长度为n的序列，最大值不超过m。 小团和小美各自选择一个[1,m]之间的整数，设小美选择的是l，小团选择的是r，我们认为两个人是默契的需要满足以下条件: 1. l小于等于r。 2. 对于序列中的元素x，如果0<x<l,或r<x<m+1,则x按其顺序保留下来，要求保留下来的子序列单调不下降。 小团为了表现出与小美最大的默契，因此事先做了功课，他想知道能够使得两人默契的二元组<l,r>一共有多少种。 我们称一个序列A为单调不下降的，当且仅当对于任意的i>j,满足A_i>=A_j。
输入第一行包含两个正整数m和n，表示序列元素的最大值和序列的长度。(1<=n,m<=100000) 输入第二行包含n个正整数，表示该序列。
输出仅包含一个整数，表示能使得两人默契的二元组数量。
5 5 4 1 4 1 2
10
考点：双指针
数据规模 n ≤ 1e5 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：双指针
本题切入点
保留的元素是「小于 l 或大于 r」的部分，要求它们整体单调不下降；据此对 l、r 做双指针/预处理边界后计数。
用两个指针协同移动，把两层循环的 O(n²) 优化到 O(n)。
思路框架（双指针 通法 · 非本题专属）
实现要点：写成 while (l < r) 循环最清晰，切记每轮至少有一个指针移动，否则死循环。
复杂度：时间 O(n)（排序则 O(n log n)） ｜ 空间 O(1)
该范式的通法易错点
对照本题
样例 1
5 5 / 4 1 4 1 210解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：美团2023校招技术第4场编程题。