「CF1167E」Range Deleting【双指针】

E. Range Deleting

time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

You are given an array consisting of $n$n integers $a_1,a_2,…,a_n$a1​,a2​,…,an​ and an integer $x$x. It is guaranteed that for every $i$i, $1\leq a_i\leq x$1≤ai​≤x.

Let’s denote a function $f(l,r)$f(l,r) which erases all values such that $l\leq a_i\leq r$l≤ai​≤r from the array $a$a and returns the resulting array. For example, if $a=[4,1,1,4,5,2,4,3],$a=[4,1,1,4,5,2,4,3], then $f(2,4)=[1,1,5].$f(2,4)=[1,1,5].

Your task is to calculate the number of pairs $(l,r)$(l,r) such that $1\leq l\leq r\leq x$1≤l≤r≤x and $f(l,r)$f(l,r) is sorted in non-descending order. Note that the empty array is also considered sorted.

Input

The first line contains two integers $n$n and $x$x $(1\leq n,x\leq 10^6)$(1≤n,x≤106) — the length of array $a$a and the upper limit for its elements, respectively.

The second line contains $n$n integers $a_1,a_2,…a_n (1\leq a_i \leq x).$a1​,a2​,…an​(1≤ai​≤x).

Output

Print the number of pairs $1\leq l\leq r\leq x$1≤l≤r≤x such that $f(l,r)$f(l,r) is sorted in non-descending order.

Examples

input

3 3
2 3 1

output

4

input

7 4
1 3 1 2 2 4 3

output

6

Note

In the first test case correct pairs are $(1,1), (1,2), (1,3)$(1,1),(1,2),(1,3) and $(2,3).$(2,3).

In the second test case correct pairs are $(1,3), (1,4), (2,3), (2,4), (3,3)$(1,3),(1,4),(2,3),(2,4),(3,3) and $(3,4).$(3,4).

题意

• 就是给你一个序列，然后你可选择两个数$l$l和$r$r使得$1\leq l\leq r \leq x$1≤l≤r≤x，使得删去序列中所有满足$l\leq a_i \leq r$l≤ai​≤r的数后序列非严格递减，问有多少对可行的$l\ r$l r，空序列满足条件

题解

• 由于非递减序列的子序列荏苒非递减，所以对于删去一段区间$[l,r]$[l,r]的数后，所有大于$r$r的数的最小位置一定大于所有小于$l$l的数的最大位置，首先可以预处理出弱删除$[1,i]$[1,i]或者$[i,x]$[i,x]的所有数后剩下的所有数是否构成非递减序列，并且分别记录剩下的数的最左边位置和最右边位置，最后枚举左端点$l$l，用另外一个指针去找最小的$r$r满足以下几个条件

  1. $r\geq l$r≥l
  2. 删去$[1,r]$[1,r]的数剩下的数非递减
  3. 删去$[1,r]$[1,r]的数剩下的数中最左边数的位置$>$>删去$[l,x]$[l,x]后剩下的数中最右边的数的位置

  然后$ans+=x-r+1$ans+=x−r+1即可

代码

#include<bits/stdc++.h>

using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e6+10;

int n,x,a[maxn],l[maxn],r[maxn];
vector<int> pos[maxn];
bool canl[maxn],canr[maxn];

int main()
{
    scanf("%d %d",&n,&x);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]].push_back(i);
    int p=inf;
    memset(canl,false,sizeof(canl));
    memset(canr,false,sizeof(canr));
    for(int i=x+1;i>=1;i--) {
        if(pos[i].empty()) {
            canl[i-1]=true;
            l[i-1]=p;
            continue;
        }
        if(pos[i].back()<=p) {
            canl[i-1]=true;
            l[i-1]=p=pos[i][0];
        }else break;
    }
    p=-1;
    for(int i=0;i<=x;i++) {
        if(pos[i].empty()) {
            canr[i+1]=true;
            r[i+1]=p;
            continue;
        }
        if(pos[i][0]>p) {
            canr[i+1]=true;
            r[i+1]=p=pos[i].back();
        }else break;
    }

    long long ans=0;int point=0;
    for(int i=1;i<=x&&canr[i];i++) {
        while(point<x&&(point<i||!canl[point]||l[point]<r[i])) point++;
        ans+=(x-point+1);
    }
    printf("%lld\n",ans);

}