小团的默契游戏

m, n = list(map(int, input().split()))
sequence = list(map(int, input().split()))

def check(sequence, l, r):
    stack = []
    for i in sequence:
        if i < l&nbs***bsp;i > r:
            if not stack&nbs***bsp;i >= stack[-1]:
                stack.append(i)
            else:
                return False
    return True

count = 0
for l in range(1,m+1):
    if not check(sequence, l, m):
        break
    for r in range(l,m+1):
        if check(sequence, l, r):
            count += m-r+1
            break
print(count)

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> &nums, int m) {
    int cnt = 0, n = nums.size();
    for (int r = m; r > 0; --r) {
        // 枚举 l 的最大可能性
        int lo = 0, hi = r, mid;  // [0, r]，0是为了方便判断 (r,m+1) 所选序列是非法的
        while (lo < hi) {
            mid = (hi - lo + 1) / 2 + lo;
            // 在 nums 中选出 (0, l) ∪ (r, m+1) 的元素并检测是否单调非降
            int pre = -1, flag = 1;  // nums[i] > 0
            for (int x: nums) {
                if (x < mid || x > r) {
                    if (x < pre) {
                        flag = 0;
                        break;
                    }
                    pre = x;
                }
            }
            if (flag) {  // 尝试把 l 放大的同时记录答案
                lo = mid;
            } else {  // 一定不是，那么把 l 减小
                hi = mid - 1;
            }
        }
        // 如果 lo = 0，证明不管怎么降低 l 都无法构成单调非降，因为 (r,m+1) 所选的子序列有问题
        if (0 == lo) break;
        cnt += lo;
    }
    return cnt;
}

int main() {
    int m, n; cin >> m >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &nums[i]);
    }
    cout << solve(nums, m) << endl;
    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        Integer m = Integer.parseInt(line[0]);
        Integer n = Integer.parseInt(line[1]);
        line = br.readLine().split(" ");
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line[i]);
        }

        int res = 0;
        int l = 1, r = m;
        while (true){
            if (judge(l, r, nums, m)) {
                r--;
            } else break;
        }
        r = r + 1;
        for (int i = r; i <= m; i++) {
            while (l <= i) {
                if (judge(l, i, nums, m)) {
                    l++;
                    res += m - i + 1;
                } else break;
            }
        }
        System.out.println(res);



    }

    private static boolean judge(int l, int r, int[] nums, int m) {//定义函数简化流程
        int tmp = 0;
        for (int num : nums) {
            if ((num > 0 && num < l) || (num < m + 1 && num > r)) {
                if (num >= tmp) tmp = num;
                else return false;
            }
        }
        return true;
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*      一种nlgn的做法：
    对于序列seq中每个元素，记它为<pos,val>，其中pos为它在序列中的编号，val为它的值大小。
    初始输入后，seq中元素按照pos升序排序，现在使用稳定排序，将它们按照val升序排序，记处理
    后的序列为arr。为了方便，令arr[0] = <0,0>，arr[n+1] = <n+1,m+1>。arr[1..n]真
    正用于保存元素。

    令：
        满足0<x<l的元素集合为A。
        满足r<x<m+1的元素集合为B。
    此时，对于任意的 l<=r：
        集合A是arr的某个前缀，集合B是arr的某个后缀，且它们显然没有交集。

    现在如果仅考虑集合A中的元素，则它们是合法的 <==> 它们的pos是升序排列的。
        因此可以预先处理arr，找出使得arr[1..P)按照pos升序的最大的P。
        这样就确定了 l<=arr[P].val。

    类似地，如果仅考虑集合B中的元素，则它们是合法的 <==> 它们的pos是升序排列的。
        因此可以预先处理arr，找出使得arr(Q..n]按照pos升序的最小的Q。
        这样就确定了 r>=arr[Q].val。

    此外，如果A和B联合起来要合法，则还需要符合：集合A中最大的pos < 集合B中最小的pos。

    现在对A和B进行搜索，寻找合法的A、B。假设A中pos最大元素为arr[p]，B中pos最小元素为arr[q]，
    则预先可以确定有这些限制：p<q , p<P , q>Q , arr[p].pos<arr[q].pos。反之只要符合这
    些限制，那么就可以得到合法的A、B，即A=arr[1..p]，B=arr[q..n]。
    （为了方便，允许p==0表示A为空集，q==n+1表示B为空集）

    接下来如何搜索合法的A和B（也就是如何搜索合法的p和q）。对于每一个[0,..P)的p，只需要在
    (max(Q,p)...n+1]中，搜索满足arr[p].pos<arr[q].pos的q（范围包含0或N+1是因为允许A、B为空集）。
    对于每一个p，arr[p].pos是一个常数，由于arr(max(Q,p),n+1]是按照pos递增的，因此可以二分搜索满足
    条件的最小的q，找到它后，任何比它大的q都是合法的。

    对于每一对合法的A=arr[1..p]，B=arr[q..n]，一定有p<q。可以确定对应的l和r：
        1、arr[p].val   < l <= arr[p+1].val
        2、arr[q-1].val <= r < arr[q].val
        3、l <= r
    （回忆：我们令arr[0].val==0、arr[n+1].val==m+1。因此当p为N或者q为1时是可以正常运算的
    此外，还允许p为0或者q为N+1，此时A或B为空集，此时仍然可以按照上述公式计算）
    这里面<l,r>的对数可以如此计算：
        |集合1| * |集合2| - |集合1 ∩ 集合2 中l>r的二元组|
        = |集合1| * |集合2| - Combination(2,|集合1 ∩ 集合2|)

    按照搜索中的顺序，对于一个固定的p，对于不同的q，上述的集合2是互不相交的，且至多存在一个
    集合2（对应搜索到符合条件的最小q的那个）会与集合1有交集。因此，对于固定p的一轮搜索，可以
    将上式聚合起来计算。
*/

class node{
public:
    int val;
    int pos;
    node(int p,int v):pos(p),val(v){}

    class val_comp{
    public:
        bool operator()(const node &a,const node &b) const{
            return a.val<b.val;
        }
    };
};

//vector<node> nodes;
vector<node> arr;
int not_found = -1;
int find_first_greater_pos_index(int pos,int from,int to){  // arr[from,to) 内找到第一个node.pos大于pos的值的下标
    if(from>=to)
        return not_found;
    if(from+1==to){
        if(arr[from].pos>pos)
            return from;
        else
            return not_found;
    }
    int mid = (from+to)/2;
    int tmp;
    if(arr[mid].pos<=pos)
        tmp = find_first_greater_pos_index(pos, mid+1, to);
    else{
        tmp = find_first_greater_pos_index(pos, from, mid);
        if(tmp==not_found)
            tmp = mid;
    }
    return tmp;
}

int main() {
    int n,m;
    cin>>n>>m;
    arr.emplace_back(0,0);
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        arr.emplace_back(i+1,tmp);
    }

    std::stable_sort(arr.begin(),arr.end(),node::val_comp());
    arr.emplace_back(n+1,m+1);  // arr[0,1...,n,n+1]
    int mx_index_arr = n + 1;

    int P,Q;
    for(P=1; P <= mx_index_arr; P++)
        if(arr[P].pos<arr[P-1].pos)
            break;

    for(Q= mx_index_arr - 1; Q > 0; Q--)
        if(arr[Q].pos>arr[Q+1].pos)
            break;

    int count = 0;
    for(int p = 0;p<P;p++){
        int q = find_first_greater_pos_index(arr[p].pos, max(Q,p)+1, mx_index_arr + 1);
        if(q==not_found)
            continue;
        int set1 = arr[p+1].val - arr[p].val;
        int set2 = arr[mx_index_arr].val - arr[q - 1].val;
        int inter_set = arr[p+1].val - arr[q-1].val - 1;
        count += set1*set2;
        if(inter_set>0)
            count -= (inter_set-1)*inter_set/2;
    }

    cout<<count;
}
// 64 位输出请用 printf("%lld")

import java.io.*;
import java.lang.*;
import java.util.*;

// 1<=x<l || r<x<=m的数都要保留下来，构成一个非递减序列
// 意思是上述两个条件任一范围内保留下来的数不能构成非递减序列，则这个数对肯定不能满足条件
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().trim().split(" ");
        int m = Integer.parseInt(params[0]);
        int n = Integer.parseInt(params[1]);
        int[] nums = new int[n];
        params = br.readLine().trim().split(" ");
        for(int i=0;i<n;++i){
            nums[i] = Integer.parseInt(params[i]);
        }
        // 1.从m开始逆序枚举r的位置，对每个r，首先判断>r的数是否能构成非递减序列，如果不能，枚举结束；
        // 2.如果r满足，则寻找满足条件的最大l，在[1,r]内二分查找。满足条件的对数增加 L 个
        int cnt = 0;
        for(int r=m;r>=1;r--){
            // 步骤1
            if(!notDecreaseWithR(nums,r)){
                break;
            }
            // 步骤2
            cnt += findMaxL(nums,r);
        }
        System.out.println(cnt);
    }

    // 判断>r的能否构成非递减序列
    public static boolean notDecreaseWithR(int[] nums,int r){
        // 留下来的前一个数
        int pre = 0;
        for(int i=0;i<nums.length;++i){
            // 如果当前nums[i]>r,但是<pre，则不能构成非递减序列
            if(nums[i] > r){
                if(nums[i] < pre){
                    return false;
                }
                pre = nums[i];
            }
        }
        return true;
    }

    // 满足1<=x<l || r<x<=m留下来的序列能够构成非递减
    public static boolean notDecreaseWithL(int[] nums,int l,int r){
        int pre = 0;
        for(int i=0;i<nums.length;++i){
            if(nums[i] > r || nums[i] < l){
                if(nums[i] < pre){
                    return false;
                }
                pre = nums[i];
            }
        }
        return true;
    }

    // 在[1,r]找到满足条件的最大 l,二分查找
    public static int findMaxL(int[] nums,int r){
        int low =1;
        int high =r;
        int maxL = 0;
        while(low<=high){
            int l = low + (high-low)/2;
            if(notDecreaseWithL(nums,l,r)){
                maxL = l;
                low = l+1;
            }else{
                high = l-1;
            }
        }
        return maxL;
    }
}

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = " ";
        while((str = br.readLine()) != null){
            String[] str_array = str.split(" ");
            int m = Integer.parseInt(str_array[0]);
            int n = Integer.parseInt(str_array[1]);
            int[] array = new int[n];
            str_array = br.readLine().split(" ");
            for(int i = 0; i < n; ++i) array[i] = Integer.parseInt(str_array[i]);
            int result = 0;
            for(int i = 1; i <= m; ++i){
                int index = function(array,m,i,i,m);
                //System.out.println("以"+i+"开头有"+(n-index+1)+"个");
                result += index == -1? 0 : (n-index+1);
            }
            System.out.println(result);
            
        }
    }
    public static int function(int[] array, int m, int left,int l, int r){//找到以left为起始位置的最小合法区间的右边界值
        int mid;
        while(l < r){
            mid = (l + r) >> 1;
            if(isVaild(array,m,left,mid)) r = mid;
            else l = mid + 1;
        }
        
        return isVaild(array,m,left,l)? l : -1;
    }
    public static boolean isVaild(int[] array, int m,int left, int right){
        int pre = Integer.MIN_VALUE;
        
        for(int value : array){
            if((value > 0 && value < left) || (value > right && value < m+1)){
                if(value < pre) return false;
                pre = value;
            }
        }
        
        
        return true;
    }
    
}

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = sc.nextInt();
        int ans = 0;
        int r = m;
        while (r > 0) {
            int cnt = 0;
            if (!check(arr, 0, r)) {
                break;
            }
            int l = 1;
            int temp = r;
            int mid = 0;
            while (l <= r) {
                mid = l + (r - l) / 2;
                if (check(arr, mid, temp)) {
                    cnt = mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            //System.out.println("r = "+temp+" cnt = "+cnt);
            r = temp - 1;
            ans += cnt;
        }
        System.out.println(ans);
    }

    public static boolean check(int[] arr, int l, int r) {
        int pre = 0;
        for (int x : arr) {
            if (x >= l && x <= r)
                continue;
            else if (x < pre)
                return false;
            else {
                pre = x;
            }
        }
        return true;
    }

}