codeforce 1076A Minimizing the String 1/5

题目链接：http://codeforces.com/contest/1076/problem/A

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".

 题意：给一个整数n，和长度为n的小写字母串，求将字母串中一个字母删除后，得到最小的串，并输出这个串。

方法：从前往后判断相邻的字母的大小，当后边字母小于前边字母时，给这个前边字母的下标打上标记，之后不输出这个字母。若整个字母串没有出现上述情况，则给最后一个字母的下标打上标记

代码：

#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
char s[200001];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        scanf("%s",s);
        int f=0,index;
        for(int i=0 ;s[i+1];i++)
        {
            if(s[i]>s[i+1])
            {
                f=1;
                index=i;
                break;
            }
        }
        if(f==0)
        {
            index=n-1;

        }
        for(int i=0 ;s[i];i++)
        {
            if(i==index)
                continue;
            printf("%c",s[i]);
        }
        printf("\n");
    }
    return 0;
}