Educational Codeforces Round 54 (Rated for Div. 2) A. Minimizing the String

大致的解题思路就是：只要后面一个字符比前面的大，就删除这个字符就好啦。越前面的字符越好。 当然也要考虑到所有字符都相等的情况。

A. Minimizing the String

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a string ss consisting of nn lowercase Latin letters.

You have to remove at most one (i.e. zero or one) character of this string in such a way that the string you obtain will be lexicographically smallest among all strings that can be obtained using this operation.

String s=s1s2…sns=s1s2…sn is lexicographically smaller than string t=t1t2…tmt=t1t2…tm if n<mn<m and s1=t1,s2=t2,…,sn=tns1=t1,s2=t2,…,sn=tn or there exists a number pp such that p≤min(n,m)p≤min(n,m) and s1=t1,s2=t2,…,sp−1=tp−1s1=t1,s2=t2,…,sp−1=tp−1 and sp<tpsp<tp.

For example, "aaa" is smaller than "aaaa", "abb" is smaller than "abc", "pqr" is smaller than "z".

Input

The first line of the input contains one integer nn (2≤n≤2⋅1052≤n≤2⋅105) — the length of ss.

The second line of the input contains exactly nn lowercase Latin letters — the string ss.

Output

Print one string — the smallest possible lexicographically string that can be obtained by removing at most one character from the string ss.

Examples

input

Copy

3
aaa

output

Copy

aa

input

Copy

5
abcda

output

Copy

abca

Note

In the first example you can remove any character of ss to obtain the string "aa".

In the second example "abca" < "abcd" < "abcda" < "abda" < "acda" < "bcda".

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a[300000+10];
int main()
{
    int n,m,j,k,i,T;
    while (cin>>n)
    {

        getchar();
        scanf("%s",a);
        int index = -1;
        for (i=0;i<n-1;i++)
        {
            if (a[i+1]<a[i])
            {
                index = i;
                break;
            }
        }
        if (index==-1)
        {
            for (i=0;i<n-1;i++)
                printf("%c",a[i]);
            printf("n");
        }
        else{

            for (i=0;i<n;i++)
            {
                if (i!=index)
                    printf("%c",a[i]);
            }
            printf("n");
        }
    }
    return 0;
}