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

const int N = 1e5+10;
int n;
int a[N],tmp[N];

void merger_sort(int l,int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;

    merger_sort(l,mid);
    merger_sort(mid+1,r);

    int k = 0 , i = l , j = mid + 1;

    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) tmp[k++] = a[i++];
        else tmp[k++] = a[j++];
    }

    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];

    for(int i = l , j = 0 ; i<=r ; i++ , j++) a[i] = tmp[j];
}

int main()
{
    cin >> n;

    for(int i = 0 ; i<n ; i++) cin >> a[i];

    merger_sort(0,n - 1);

    for(int i = 0 ; i<n ; i++) cout << a[i] << " ";

    return 0;
}

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

const int N = 1e5+10;
int n;

struct Range
{
    int l,r;

    bool operator<(const Range &w) const        
    {
        return l < w.l;         //按左端点从小到大排序
    }
}range[N];

int main()
{
    cin >> n;

    for(int i = 0 ; i<n ; i++) cin >> range[i].l >> range[i].r;

    sort(range,range+n);

    priority_queue<int,vector<int>,greater<int>> heap;  //建立小根堆
                    //用小根堆维护每个组里面的最大的右端点值（也就是最后一个被加进来的右端点的值）
    for(int i = 0 ; i<n ; i++)
    {
        auto r = range[i];
        if(heap.empty() || heap.top() >= r.l) heap.push(r.r); //堆空或者现在所有组中最小的右端点值   
        else    //比现在遍历到的这个区间的左端点大（说明他和所有的组都有交集），直接让他的右端点进堆（新建一个组）
        {
            heap.pop();     //进else说明堆不空，所有组中最小的右端点是在这个区间的左边（说明存在组和
            heap.push(r.r); //这个区间没有交集）直接把他加到第一组中（就是现在堆顶的这一组，加第几组
        }       //都无所谓），把堆顶的最大右端点更新成现在这个区间的右端点就算添加成功（小根堆会自动排序维护）
    }

    cout << heap.size();

    return 0;
}

#include <iostream>         //跟上一题的区间选点的代码是一样的
#include <algorithm>        //因为选点选的是最少的点但是包含的所有区间，而不相交区间就相当于把选的一个
using namespace std;        //点当作的一个区间，因为这个点实际包含在很多个区间中

const int N = 1e5+10;
int n;

struct range
{
    int l,r;
    bool operator<(const range &w) const
    {
        return r < w.r;
    }
}range[N];

int main()
{
    cin >> n;
    for(int i = 0 ; i<n ; i++) cin >> range[i].l >> range[i].r;

    sort(range,range+n);

    int res = 0 , ed = -2e9;
    for(int i = 0 ; i<n ; i++) 
    {
        if(range[i].l > ed)
        {
            res++;
            ed = range[i].r;
        }
    }

    cout << res;

    return 0;
}

#include <iostream>             //每个区间按右端点从小到大排，然后遍历看下一个区间的左端点是否大于 
#include <algorithm>            //现在的右端点（不大于说明有交集，大于就是空集，就把最大的右端点更新出来）
using namespace std;

const int N = 1e5+10;
int n;

struct range
{
    int l,r;

    bool operator<(const range &w) const
    {
        return r < w.r;
    }
}range[N];

//bool cmp(Range a,Range b){
//    return a.r<b.r;
//}

int main()
{
    cin >> n;

    for(int i = 0 ; i<n ; i++) cin >> range[i].l >> range[i].r;

    sort(range,range+n);            //在结构体中重载<号的排序
    //sort(range,range+n,cmp);      //在外面定义一个判断函数的排序

    int res = 0 , ed = -2e9;

    for (int i = 0 ; i<n ; i++)
    {
        if(range[i].l > ed)
        {
            res++;
            ed = range[i].r;
        }
    }

    cout << res;

    return 0;
}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool check(int date)    //判断日期是否符合要求的函数
{
    int year = date / 10000;
    int month = date % 10000 / 100;
    int day = date % 100;

    if (!month || month >= 13 || !day) return false;

    if (month != 2 && day > months[month]) return false;
    if (month == 2)
    {
        bool leap = year % 4 == 0 && year % 100 || year % 400 == 0;
        if (day > 28 + leap) return false;
    }

    return true;
}

int main()
{
    int date1, date2;
    cin >> date1 >> date2;

    int res = 0;                
    for (int i = 1000; i < 10000; i ++ )    //只遍历年份的前四位，然后依据前四位求出后四位
    {                                       //在判断整体是否符合日期的形式
        int x = i, r = i;
        for (int j = 0; j < 4; j ++ ) r = r * 10 + x % 10, x /= 10; //依据前四位求整体

        if (r >= date1 && r <= date2 && check(r)) res ++ ; //判断所求的日期是否符合要求
    }

    printf("%d\n", res);
    return 0;
}

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

const int N = 1e8+10;
int n;
int a[N];
int num,res1,res2;


int main()
{
    cin >> n;
    while(cin >> a[num]) num++;

    sort(a,a+num);

    for(int i = 1 ; i<num ; i++)
    {
        if(a[i] == a[i-1] + 2) res1 = a[i] - 1;
        if(a[i] == a[i-1]) res2 = a[i];
    }

    cout << res1 << " " << res2;

    return 0;
}

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

const int N = 1e4+10;
int n;

int main()
{    
    cin >> n;

    int sum = 0;
    for(int i = 1 ; i<=n ; i++)
    {
        int t = i;
        while(t)
        {
            if(t%10 == 1 || t%10 == 2 || t%10 == 0 || t%10 == 9)
            {
                sum += i;
                break;
            }
            t /= 10;
        }
    }

    cout << sum;

    return 0;
}

#include <iostream>     //大概可以理解为一条数轴上的点是所有的abc的可能取值，然后cnt就是让数轴上的点的y++，表示这个
#include <algorithm>    //数的个数，然后求出前缀和之后和b作比较，把b遍历一遍，在b前面就是比b小，c同理
#include <cstring>
using namespace std;

typedef long long LL;

const int N = 1e5+10;
int n;
int a[N],b[N],c[N];  
int cnt[N],as[N],cs[N],s[N];    //as和cs用来存当前b[i]所对应的位置上有多少个符合条件的a和c
                                //cnt用来存a和c中每个元素的个数
int main()                      //s用来存cnt的前缀和
{
    cin >> n;

    for(int i = 0 ; i<n ; i++) cin >> a[i];     //这里读入后应该要++的（a[i]++）因为实际待会求s的时候是从1开始遍历的
    for(int i = 0 ; i<n ; i++) cin >> b[i];     //但这题的数据没卡这个。可能还有其他原因把
    for(int i = 0 ; i<n ; i++) cin >> c[i];

    for(int i = 0 ; i<n ; i++) cnt[a[i]]++;     //记录每个a[i]有几个，放入cnt中有点像桶排，哈希表的思想
    for(int i = 0 ; i<N ; i++) s[i] = s[i-1] + cnt[i];  //求cnt的前缀和
    for(int i = 0 ; i<n ; i++) as[i] = s[b[i] - 1];     //表示比第一个b的值还要小的a的数量
                                                //在求cnt的过程中其实已经可以看作把a和c排好序了，因为把数放到相应位置
    memset(cnt , 0 , sizeof cnt);               //小的在前
    memset(s , 0 , sizeof s);       //还原cnt和s然后求cs

    for(int i = 0 ; i<n ; i++) cnt[c[i]]++;
    for(int i = 0 ; i<N ; i++) s[i] = s[i-1] + cnt[i];
    for(int i = 0 ; i<n ; i++) cs[i] = s[N - 1] - s[b[i]];  //c要求的是比b大的c的数量，所以用s[N - 1] 可能能达到的最
                                                            //大的数，减去s[b[i]]也就是比b小的数
    LL res = 0;     //这里会爆int

    for(int i = 0 ; i<n ; i++) res += (LL)as[i] * cs[i];

    cout << res;

    return 0;
}

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

const int N = 1e4+10;
int n,res;
int a[N];

int main()
{
    cin >> n;
    for(int i = 0 ; i<n ; i++) cin >> a[i];

    for(int i = 0 ; i<n ; i++)
    {
        int minx = a[i] , maxx = a[i];

        for(int j = i ; j<n ; j++)
        {
            maxx = max(maxx,a[j]);
            minx = min(minx,a[j]);
            if(maxx - minx == j - i) res++;     //因为每个序列都是1到N中的数，差值都为1，不会重复，
        }                                       //所在i到j的区间中最大值减去最小值就等与这个区间元素个数减1
    }

    cout << res;

    return 0;
}

#include <iostream>
#include <sstream> //包含了下面的stringstream
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int n,cnt,res1,res2;
int a[N];
string line;

int main()
{
    cin >> cnt;
    getline(cin , line);    //上面的行数读完后会有一个回车，所以这里先把回车读掉（getline是会读回车的）

    while(cnt--)
    {
        getline(cin , line);  
        stringstream s(line);   //定义了一个读取字符串的s用来读这一行的line，定义完后用法的cin一样

        while(s >> a[n]) n++;       //把line里的东西读到a[n] 中
    }

    sort(a,a+n);

    for(int i = 1 ; i<n ; i++)
    {
        if(a[i] == a[i-1]) res2 = a[i];
        if(a[i] == a[i-1] + 2) res1 = a[i] - 1;
    }

    cout << res1 << " " << res2;

    return 0;
}