// Original C++ solution (slower):
//

//  2019/03/30 Ver1.10

//

//  Codeforces: ganariya

//  AtCoder: ganariya2525

//  MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMHBYYYWMMMM#BYYTTTYWMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMB9O1==?????zzCC111>>;;;;;;;;;;;<?TMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMMMMMMM9Olll=l======??????????>>>>>>;;;;;;;;;:;?TMMMMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMMMM9ttlllllllll=l=======?????????>>>>>>;;;;;;;;;;?TMMMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMMMBOttOtttttltlllllllll=======??????????>>>>>>>;;;;;;?TMMMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMMMBttwOtttttttttttttlllllllll========?????????>>>>>>;;;;;<TMMMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMMBrwZrttttttttttttttttttlllllllllll======???????????>>>>>>;;?HMMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMMSw0trtrrtrtrttrtttttttttttttlllOllllll========????<<zz??>>>>>>ZMMMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMMMX0ttrtrOOttrttrttOOttttttttttttltwllllllllll========??wy?????>>>vZMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMM0ttrI+wV1rtttttttwZtttttttltttOwylOXOllllllllllll=l====1dkz???????vZdMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMSrrwrtwZCjttttttttwSttOlllltllllwtXOlZkOlllllllllllllll==z+dk===?????X2JMMMMMMMMMMMMM

//  MMMMMMMMMMMMMBrtwwtrw0<jttttttttOXllOttltllttllOZwHOtXkyltlllllllllllllll<+XZ======?dk?JMMMMMMMMMMMM

//  MMMMMMMMMMMMStwdZtwXC<+ttttttOOOd6ltZlltllllttllStWWOOHWytttttltltOllltllz:zHllll===zX=?dMMMMMMMMMMM

//  MMMMMMMMMMBrwdKOtwW3;;zrttttwZwXRlldOllltltlltttwlXvktdXWytltttttttOttlttl<<dklllllllZ===dMMMMMMMMMM

//  MMMMMMMMM8tQM#ttwW3;;;1trttwSwfUOlORltllltlllllldtX>dktDOWOtlttltttOOttltO<;+WOllllllXlllzMMMMMMMMMM

//  MMMMMMMM9OdM#Ottd$;;;;;<?1z0OKjRltd0llltOllllllldZX>?WOw_WWOtttttttttOttI<;;<dkttttllllllldMMMMMMMMM

//  MMMMMMM9wMMMSttwS<;;;;>;;;J<j>(I<?U111zltllllllld0X>~dkwl(WkttlttlOOwWk<;;:;;zHttttttwOllllMMMMMMMMM

//  MMMMMMBdMMM8tttdI+zttttttdSXt~dlzXwlllzzOzzzzzlldkW<~?kOk~?sx++++jdHmH6+++<;;jdZtttttdkOtlldMMMMMMMM

//  MMMMM#dMMM#tttw0+tttttttdKdf((RsdfRllllldZllltlldWK~~_W0w_~OWOlOdgg9ZtOWOtttz+wktttttdpktttwMMMMMMMM

//  MMMMMWMMMMSlttdIttttttOdWHH>~(IzWDRll=llzRlllzlldk$>++dkd<~_XkdgH9tttttdktttt+OkrttrtdfpkttOMMMMMMMM

//  MMMMNWMMM#Zttlk=tttttOXWWd$_.(IdW1R=llll=SlllzOldK<_._(kd6+-(MM9lltttttrWktttztWZttrwXppWttrMMMMMMMM

//  MMMMNMMMM#lltwDzttllOXyW0X:..(OXk<Rl=ll=lwOlllOld3<``.(Rd>~?CdklllltttttXdXttzOWktrwwWpfpkrtMMMMMMMM

//  MMMMMMMMM@ltldIzlttOXyW$w$```(OyD(Rl==llldZ=llIlw;~```-Xd:~~~~UkylltttAyHdgSrzObRtOXwpfppWrrMMMMMMMM

//  MMMMMMMMM@llldtlllldVyW+d>```.wZ$ wl==lI=wRl=ll=w<```` dd_..~~(RZXOQdggHH9ZwrzwHWrdXXppfppkrMMMMMMMM

//  MMMMMMMMM#llldlltlwyyyD(S-...,Wk] zI=l=llzWzl=l=P~```` jZ``...~zQkH@MBUtrZtrtldHRdSdpfpffpkwMMMMMMMM

//  MMMMNMMMMNZllXtllldVyW3(Mf=<ONMHP~(k===l=zdk=lld3```...(C````..(M96lttttrrtrrtdHWHXpfpppfpRwMMMMMMMM

//  MMMMMMMMMMNzzWZllzyyyy(W@`  =~MWK6 jz=lzlzvRz=lZ`.I+JgkWm&-. `..(ZltlttttrtttrWWHppfppfpppSdMMMMMMMM

//  MMMMMMMMMMMkAWRllzVyyS_(b    .MNHU-(Uz=lI={XkzO>.dVT7<TMHMNHHx-.(kwZyltttrtrrdHHpfppfpffpp0dMMMMMMMM

//  MMMMMMMMMMMMKyWzOzyyyk.`<!  hdWMH]``(S==t=l(kX2 ?_`    WMMHH#HH+.XwkwOttttrwrZ~(HfpfpppfpWwXMMMMMMMM

//  MMMMMMMMMMMMMHWROOyyyW;` `. (WVM#b```(0=zzz wX!```  a.dM#NM@N(4WhXkXkWtttttwd3O_(HpffpfpfWwSMMMMMMMM

//  MMMMMMMMMMMMNZvWzXXyyXP```-_ ?o+?!````.4=Z=`(:````  HpbNNMHHH (C=XXyWZWttrdwf:(>.dfppffppSXSMMMMMMMM

//  MMMMMMMMMMMMMRzuHzXyZXH.``````````````` ?zz ``````` ZKvTHHbWt `` XZyyHZWOdSZ<::~`(fpfpfffXp0WMMMMMMM

//  MMMMMMMMMMMMMKzyyHvyZZW____.`````````````.I_```````` ?nJzX7^````.WXWyyHyWKZ<:::_`Jffpfpfpfp0WMMMMMMM

//  MMMMMMMMMMMMM@zZyZWwWyXo-_~(~ ```````````` `````````````` _`````.WXkyyVWmWc::<~ .HffppfffffkXMMMMMMM

//  MMMMMMMMMMMMMKzZZZZXkUXr~....```````....```````````` ...  ````..JXWWyyW83vXx~..WfffVfWVffffkdMMMMMMM

//  MMMMMMMMMMMMMRzZZZZZZZZb````````````<````````````./<~._<_.____`(WfdyW3<:~~(XWkVVVVVVVHVVVVV0dMMMMMMM

//  MMMMMMMMMMMMMSzZZZZZZZWX-```````````````````````````.......~~._j9jX=_~~_(XZyVHHkyyyyWHyyykykOMMMMMMM

//  MMMMMMMMMMMMMSzuuuuuZXWZW,```````````````````````````````.``..(3<! ...JWyyXWyyyWHkyyWHyyyHyklMMMMMMM

//  MMMMMMMMMMMMNXzuuuXXuXSuuXh,```````` .... ```````````````````_~ .JWyyyyZyy0HyyZyyZyZXWZZZWHZIdMMMMMM

//  MMMMMMMMMMMMNwtuuuXkuXXuuuuXh,``````(:::~<?71(,``````````````.(UMNUkZZZZZZZHZZ0ZZZZZWWZZZWNXIdMMMMMM

//  MMMMMMMMMMMMNKOzuzXkuXuuuuuXuXW, ```` _~~~:~~(}```````````.(YC;::<kCfZZZZXO#ZZVZZZZZMZZuuMMNXzMMMMMM

//  MMMMMMMMMMMMHKOzzuXkzdzzzzuXXzuuU&.``````````````````` .JY>::::;;J=:dZuZuZd#uuruuuud#uuuXMMMNXdMMMMM

//  MMMMMMMMMMMMMNOvzzXkvMRzzzzXKzuzzzXh, `````````````..JC<;:;;:;;+7<:~(HHuXIdNuuzuuuXMSuuuWMMMMROMMMMM

//  MMMMMMMMMMMMMNvvvrdkvM#vzzzzHzzzzzuzzUG. ``` ...JdY<:;:;:::;;+v<~~~:(HpHmzMNXZzuzzd#zzzdMMMMMMRdMMMM

//  MMMMMMMMMMMMMNwrrvdRrMNwvvvvdRvvvzwkzzzzXWWHY=~~O+::::::::<+<~~~~~~~dppppWMMkZzzzwM#zzdMMMMMMMMNMMMM

//  MMMMMMMMMMMMMM#rrrwRrMMbOrrOZNkrvvvXwvvvvvwX;.~._W_:::::(?!~~~~~~~~(HpppppppHWdvwM#XwdMMMMMMMMMMNMMM

//  MMMMMMMMMMMMMMNyrrrRrWMMmzOrzdNyrrrZNvrwQWWfb....(r~~_J>_.....~.~~-dpfpffpfpppWHHMNdMMMMMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMNrtrStdMMMNxzrzMNmrrrdNWfVfffP._-.(~_J!............JpfpffpfpfffpppWNppppHMMMMMMMMMMMM

//  MMMMMMMMMMMMMMMMNOtXtdMMMMMNxzZMMNmgHyVVVVVW%..?/(.,(x-..........(HfffpffpffpffWHHffpffppfVyyWMMMMMM





//include

//------------------------------------------

#include <vector>

#include <list>

#include <map>

#include <climits>

#include <set>

#include <unordered_set>

#include <unordered_map>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

#include <queue>

#include <random>

#include <cctype>

#include <complex>

#include <regex>

#include <unordered_map>





using namespace std;



//typedef

//------------------------------------------

typedef long long LL;

typedef vector<int> VI;

typedef vector<bool> VB;

typedef vector<char> VC;

typedef vector<double> VD;

typedef vector<string> VS;

typedef vector<LL> VLL;

typedef vector<VI> VVI;

typedef vector<VB> VVB;

typedef vector<VS> VVS;

typedef vector<VLL> VVLL;

typedef vector<VVI> VVVI;

typedef vector<VVLL> VVVLL;

typedef pair<int, int> PII;

typedef pair<LL, LL> PLL;

typedef pair<int, string> PIS;

typedef pair<string, int> PSI;

typedef pair<string, string> PSS;

typedef vector<PII> VPII;

typedef vector<PLL> VPLL;

typedef vector<VPII> VVPII;

typedef vector<VPLL> VVPLL;

typedef vector<VS> VVS;

typedef map<int, int> MII;

typedef map<LL, LL> MLL;

typedef map<string, int> MSI;

typedef map<int, string> MIS;

typedef __int128 Lint;



//数値・文字列

//------------------------------------------

inline int toInt(string s) {

    int v;

    istringstream sin(s);

    sin >> v;

    return v;

}



inline LL toLongLong(string s) {

    LL v;

    istringstream sin(s);

    sin >> v;

    return v;

}



Lint toLint(const string s) {

    Lint ret = 0;

    for (int i = 0; i < s.length(); i++)

        if ('0' <= s[i] && s[i] <= '9')

            ret = 10 * ret + s[i] - '0';

    return ret;

}



template<class T>

inline string toString(T x) {

    ostringstream sout;

    sout << x;

    return sout.str();

}



inline VC toVC(string s) {

    VC data(s.begin(), s.end());

    return data;

}



vector<string> SPRIT(const string &s, const string &delim) {

    vector<string> result;

    string::size_type pos = 0;

    while (pos != string::npos) {

        string::size_type p = s.find(delim, pos);

        if (p == string::npos) {

            result.push_back(s.substr(pos));

            break;

        } else {

            result.push_back(s.substr(pos, p - pos));

        }

        pos = p + delim.size();

    }

    return result;

}



string TRIM(const string &str, const char *trimCharacterList = " \t\v\r\n") {

    string result;

    string::size_type left = str.find_first_not_of(trimCharacterList);

    if (left != string::npos) {

        string::size_type right = str.find_last_not_of(trimCharacterList);

        result = str.substr(left, right - left + 1);

    }

    return result;

}



string REPLACE_STRING(const string source, const string find, const string alt) {

    string result = source;

    string::size_type pos = 0;

    while (pos = result.find(find, pos), pos != string::npos) {

        result.replace(pos, find.length(), alt);

        pos += alt.length();

    }

    return result;

}



template<typename T>

bool VECTOR_EXISTS(vector<T> vec, T data) {

    auto itr = std::find(vec.begin(), vec.end(), data);

    size_t index = distance(vec.begin(), itr);

    if (index != vec.size())return true;

    else return false;

}



template<typename T>

void VECTOR_REMOVE_VALUE_ALL(vector<T> &vec, T data) {

    vec.erase(remove(vec.begin(), vec.end(), data), vec.end());

}



template<typename T>

vector<T> VECTOR_REMOVE_VALUE_ALL_FAST(vector<T> vec, T data) {

    vector<T> vec2;

    for (auto &x: vec) if (x != data) vec2.push_back(x);

    return vec2;

}



bool REG_MATCH(string const &text, regex const &re) {

    bool result = regex_match(text, re);

    return result;

}



bool REG_MATCH(string const &text, smatch &match, regex const &re) {

    bool result = regex_match(text, match, re);

    return result;

}



smatch REG_SEARCH(string const &text, regex const &re) {

    smatch m;

    regex_search(text, m, re);

    return m;

}



vector<smatch> REG_ALL_SEARCH(string const &text, regex const &re) {

    vector<smatch> matchs;

    sregex_iterator iter(text.cbegin(), text.cend(), re);

    sregex_iterator end;

    for (; iter != end; iter++) matchs.push_back(*iter);

    return matchs;

}



string REG_REPLACE(string const &text, regex const &re, string const &replace) {

    string result = regex_replace(text, re, replace, regex_constants::format_first_only);

    return result;

}



string REG_ALL_REPLACE(string const &text, regex const &re, string const &replace) {

    string result = regex_replace(text, re, replace);

    return result;

}



template<typename T>

vector<T> COMPRESS(vector<T> v) {

    sort(v.begin(), v.end());

    v.erase(unique(v.begin(), v.end()), v.end());

    return v;

}



template<typename T>

pair<map<T, int>, map<int, T>> MAPPING(const vector<T> v) {

    map<T, int> zip;

    map<int, T> unzip;

    for (int i = 0; i < v.size(); i++) zip[v[i]] = i;

    for (int i = 0; i < v.size(); i++) unzip[i] = v[i];

    return make_pair(zip, unzip);

}



template<typename T>

vector<pair<T, int>> RUN_LENGTH(const vector<T> &v) {

    vector<pair<T, int>> ret;

    int len = v.size();

    for (int i = 0, j = 0; i < len; i = j) {

        while (j < len && v[i] == v[j]) j++;

        ret.push_back(make_pair(v[i], j - i));

    }

    return ret;

}



template<typename T, typename U, typename V, typename W>

auto operator+(const std::pair<T, U> &l, const std::pair<V, W> &r) -> std::pair<decltype(l.first + r.first), decltype(l.second + r.second)> {

    return {l.first + r.first, l.second + r.second};

}



template<typename T, typename U, typename V, typename W>

auto operator-(const std::pair<T, U> &l, const std::pair<V, W> &r) -> std::pair<decltype(l.first - r.first), decltype(l.second - r.second)> {

    return {l.first - r.first, l.second - r.second};

}



ostream &operator<<(ostream &dest, __int128_t value) {

    ostream::sentry s(dest);

    if (s) {

        __uint128_t tmp = value < 0 ? -value : value;

        char buffer[128];

        char *d = std::end(buffer);

        do {

            --d;

            *d = "0123456789"[tmp % 10];

            tmp /= 10;

        } while (tmp != 0);

        if (value < 0) {

            --d;

            *d = '-';

        }

        int len = std::end(buffer) - d;

        if (dest.rdbuf()->sputn(d, len) != len) {

            dest.setstate(ios_base::badbit);

        }

    }

    return dest;

}





#define UPPER(s) transform((s).begin(), (s).end(), (s).begin(), ::toupper)

#define LOWER(s) transform((s).begin(), (s).end(), (s).begin(), ::tolower)





//四捨五入 nLen=小数点第n位にする

//------------------------------------------



//切り上げ

double ceil_n(double dIn, long long nLen) {

    double dOut;

    dOut = dIn * pow(10.0, nLen);

    dOut = (double) (long long) (dOut + 0.9);

    return dOut * pow(10.0, -nLen);

}



//切り捨て

double floor_n(double dIn, long long nLen) {

    double dOut;

    dOut = dIn * pow(10.0, nLen);

    dOut = (double) (long long) (dOut);

    return dOut * pow(10.0, -nLen);

}



//四捨五入

double round_n(double dIn, long long nLen) {

    double dOut;

    dOut = dIn * pow(10.0, nLen);

    dOut = (double) (long long) (dOut + 0.5);

    return dOut * pow(10.0, -nLen);

}



//n桁目の数の取得

int take_a_n(LL num, int n) {

    string str = toString(num);

    return str[str.length() - n] - '0';

}



int bitcount32(int bits) {

    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);

    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);

    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);

    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);

    return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);

}



//整数を2進数表記したときの1の個数を返す

LL bitcount64(LL bits) {

    bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);

    bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);

    bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);

    bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);

    bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);

    return (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);

}





//comparison

//------------------------------------------

#define C_MAX(a, b) ((a)>(b)?(a):(b))

#define C_MIN(a, b) ((a)<(b)?(a):(b))

#define C_ABS(a, b) ((a)<(b)?(b)-(a):(a)-(b))



template<class T1, class T2>

inline bool chmin(T1 &a, T2 b) {

    if (a > b) {

        a = b;

        return true;

    }

    return false;

}



template<class T1, class T2>

inline bool chmax(T1 &a, T2 b) {

    if (a < b) {

        a = b;

        return true;

    }

    return false;

}



//container util

//------------------------------------------

#define ALL(a)  (a).begin(),(a).end()

#define RALL(a) (a).rbegin(), (a).rend()

#define SZ(a) int((a).size())

#define EACH(i, arr) for(typeof((arr).begin()) i=(arr).begin(); i!=(arr).end(); ++i)

#define EXIST(str, e) ((str).find(e)!=(str).end())

#define COUNT(arr, v) count((arr).begin(), (arr).end(), v)

#define SEARCH(v, w) search((v).begin(), (v).end(), (w).begin(), (w).end())

#define B_SEARCH(arr, v) binary_search((arr).begin(), (arr).end(), v)

#define SORT(c) sort((c).begin(),(c).end())

#define RSORT(c) sort((c).rbegin(),(c).rend())

#define REVERSE(c) reverse((c).begin(), (c).end())

#define ROTATE_LEFT(arr, c) rotate((arr).begin(), (arr).begin()+(c), (arr).end())

#define ROTATE_RIGHT(arr, c) rotate((arr).rbegin(), (arr).rbegin() + (c), (arr).rend())

#define SUMI(arr) accumulate((arr).begin(), (arr).end(), 0)

#define SUMD(arr) accumulate((arr).begin(), (arr).end(), 0.)

#define SUMLL(arr) accumulate((arr).begin(), (arr).end(), 0LL)

#define SUMS(arr) accumulate((arr).begin(), (arr).end(), string())

#define MULD(arr) accumulate((arr).begin(), (arr).end(), 1., multiplies<double>())

#define MULLL(arr) accumulate((arr).begin(), (arr).end(), 1LL, multiplies<long long>())

#define UB(arr, n) upper_bound((arr).begin(), (arr).end(), n)

#define LB(arr, n) lower_bound((arr).begin(), (arr).end(), n)

#define OF_ALL(arr, func) all_of((arr).begin(), (arr).end(), (func))

#define OF_NONE(arr, func) none_of((arr).begin(), (arr).end(), (func))

#define OF_ANY(arr, func) any_of((arr).begin(), (arr).end(), (func))

#define PB push_back

#define MP make_pair

#define ft first

#define sd second







//input output

//------------------------------------------

#define GL(s) getline(cin, (s))

#define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0);

#define OUT(d) std::cout<<(d)

#define OUT_L(d) std::cout<<(d)<<endl

#define FOUT(n, data) std::cout<<std::fixed<<std::setprecision(n)<<(data)

#define FOUT_L(n, data) std::cout<<std::fixed<<std::setprecision(n)<<(data)<<"\n"

#define EL() printf("\n")

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}

#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

#define Yes() printf("Yes\n")

#define No() printf("No\n")

#define YES() printf("YES\n")

#define NO() printf("NO\n")

#define Yay() printf("Yay!\n")

#define Nnn() printf(":(\n")





template<typename T1, typename T2>

istream &operator>>(istream &in, pair<T1, T2> &p) {

    in >> p.first >> p.second;

    return in;

}



template<typename T>

istream &operator>>(istream &in, vector<T> &v) {

    for (auto &x: v)

        in >> x;

    return in;

}



istream &operator>>(istream &in, Lint &d) {

    string s;

    cin >> s;

    Lint tmp = 0;

    for (int i = 0; i < s.length(); i++)if ('0' <= s[i] && s[i] <= '9')tmp = 10 * tmp + s[i] - '0';

    d = tmp;

    return in;

}



template<typename T1, typename T2>

ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) {

    out << "[" << p.first << ", " << p.second << "]" << "\n";

    return out;

}





//repetition

//------------------------------------------

#define FOR(i, a, b) for(int i=(a);i<(b);++i)

#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)

#define REP(i, n)  FOR(i,0,n)

#define RREP(i, n) for(int i = n-1;i >= 0;i--)

#define FORLL(i, a, b) for(LL i=LL(a);i<LL(b);++i)

#define RFORLL(i, a, b) for(LL i=LL(b)-1;i>=LL(a);--i)

#define REPLL(i, n) for(LL i=0;i<LL(n);++i)

#define RREPLL(i, n) for(LL i=LL(n)-1;i>=0;--i)

#define FOREACH(x, arr) for(auto &(x) : (arr))

#define FORITER(x, arr) for(auto (x) = (arr).begin(); (x) != (arr).end(); ++(x))





//constant

//--------------------------------------------

const double EPS = 1e-10;

const double PI = acos(-1.0);

const int dx[] = {-1, 0, 1, 0};

const int dy[] = {0, 1, 0, -1};





//math

//--------------------------------------------



//min <= aim <= max

template<typename T>

inline bool BETWEEN(const T aim, const T min, const T max) {

    if (min <= aim && aim <= max) {

        return true;

    } else {

        return false;

    }

}



template<typename T1, typename T2>

inline bool IS_OUT(const T1 toY, const T1 toX, const T2 H, const T2 W) {

    return (toY < 0 || toY >= H || toX < 0 || toX >= W);

}



template<class T>

inline T SQR(const T x) { return x * x; }



template<class T1, class T2>

inline T1 POW(const T1 x, const T2 y) {

    if (!y)return 1;

    else if ((y & 1) == 0) {

        return SQR(POW(x, y >> 1));

    } else return POW(x, y ^ 1) * x;

}





template<typename T>

constexpr T ABS(T x) {

    return x < 0 ? -x : x;

}



//partial_permutation nPr 順列

//first・・最初の数

//middle・・r(取り出す数)

//last・・n(全体数)

template<class Iter>

bool next_partial_permutation(Iter first, Iter middle, Iter last) {

    reverse(middle, last);

    return next_permutation(first, last);

}



//combination nCr 組み合わせ

//first1・・最初の数

//last1==first2・・r(取り出す数)

//last2・・n(全体数)

template<class Iter>

bool next_combination(Iter first1, Iter last1, Iter first2,

                      Iter last2) {

    if ((first1 == last1) || (first2 == last2)) {

        return false;

    }

    Iter m1 = last1;

    Iter m2 = last2;

    --m2;

    while (--m1 != first1 && !(*m1 < *m2)) {

    }

    bool result = (m1 == first1) && !(*first1 < *m2);

    if (!result) {

        while (first2 != m2 && !(*m1 < *first2)) {

            ++first2;

        }

        first1 = m1;

        std::iter_swap(first1, first2);

        ++first1;

        ++first2;

    }

    if ((first1 != last1) && (first2 != last2)) {

        m1 = last1;

        m2 = first2;

        while ((m1 != first1) && (m2 != last2)) {

            std::iter_swap(--m1, m2);

            ++m2;

        }

        std::reverse(first1, m1);

        std::reverse(first1, last1);

        std::reverse(m2, last2);

        std::reverse(first2, last2);

    }

    return !result;

}









//numeric_law

//--------------------------------------------



template<typename T>

constexpr bool ODD(T x) {

    return x % 2 != 0;

}



template<typename T>

constexpr bool EVEN(T x) {

    return x % 2 == 0;

}



//最大公約数

template<class T>

inline T GCD(const T x, const T y) {

    if (x < 0)return GCD(-x, y);

    if (y < 0)return GCD(x, -y);

    return (!y) ? x : GCD(y, x % y);

}



//最小公倍数

template<class T>

inline T LCM(const T x, const T y) {

    if (x < 0)return LCM(-x, y);

    if (y < 0)return LCM(x, -y);

    return x * (y / GCD(x, y));

}



//ax + by = gcd(a, b)

//x,yが変数に格納される

template<class T>

inline T EXTGCD(const T a, const T b, T &x, T &y) {

    if (a < 0) {

        T d = EXTGCD(-a, b, x, y);

        x = -x;

        return d;

    }

    if (b < 0) {

        T d = EXTGCD(a, -b, x, y);

        y = -y;

        return d;

    }

    if (!b) {

        x = 1;

        y = 0;

        return a;

    } else {

        T d = EXTGCD(b, a % b, x, y);

        T t = x;

        x = y;

        y = t - (a / b) * y;

        return d;

    }

}



//mの世界でのaの逆元

//gce(a, m) = 1

template<class T>

inline T INV_MOD(const T a, const T m) {

    T x, y;

    EXTGCD(a, m, x, y);

    return (x + m) % m;

}



template<class T>

inline bool ISPRIME(const T x) {

    if (x <= 1)return false;

    for (T i = 2; i * i <= x; i++)if (x % i == 0)return false;

    return true;

}



template<class T>

VB ERATOSTHENES(const T n) {

    VB arr(n + 1, true);

    arr[0] = arr[1] = false;

    for (T i = 2; i * i <= n; i++) {

        if (arr[i]) {

            for (T j = i * 2LL; j <= n; j += i) {

                arr[j] = false;

            }

        }

    }

    return arr;

}



// a <= x < b の素数を返す

template<typename T>

VB ERATOSTHENES(const T a, const T b) {

    VB small = ERATOSTHENES(b);

    VB prime(b - a, true);



    for (T i = 2; i * i <= b; i++) {

        if (small[i]) {

            for (T j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) {

                prime[j - a] = false;

            }

        }

    }



    return prime;

}



//nの約数

template<typename T>

vector<T> DIVISOR(T n) {

    vector<T> v;

    for (T i = 1; i * i <= n; ++i) {

        if (n % i == 0) {

            v.push_back(i);

            if (i != n / i) {

                v.push_back(n / i);

            }

        }

    }

    sort(v.begin(), v.end());

    return v;

}



//nまでのすべての約数

template<typename T>

vector<vector<T>> DIVISOR_ALL(T n) {

    vector<vector<T>> res(n + 1);

    for (T i = 1; i <= n; i++) {

        for (T j = i; j <= n; j += i) {

            res[j].push_back(i);

        }

    }

    return res;

}



template<typename T>

vector<pair<T, T>> FACTORIZATION(T x) {

    vector<pair<T, LL>> ans;

    for (T i = 2; i * i <= x; i++) {

        if (x % i == 0) {

            T count = 0;

            while (x % i == 0) {

                count++;

                x /= i;

            }

            ans.push_back(MP(i, count));

        }

    }

    if (x != 1) ans.push_back(MP(x, 1));

    return ans;

}



LL POW_MOD(LL N, LL P, LL M) {

    LL ret = 1;

    while (P > 0) {

        if (P & 1LL) ret = (ret * N) % M;

        N = (N * N) % M;

        P >>= 1LL;

    }

    return ret;

}



template<typename T>

inline T NCR(T n, T r) {

    if (r > n - r) r = n - r;

    T ans = 1LL;

    for (T i = 0; i < r; i++) {

        ans = ans * (n - i) / (i + 1);

    }

    return ans;

}



LL NCR_MOD(LL n, LL r, LL M) {

    if (r > n - r) return NCR_MOD(n, n - r, M);

    LL numerator = 1LL; //分子

    LL denominator = 1LL; //分母

    for (LL i = 0; i < r; i++) {

        numerator *= (n - i);

        numerator %= M;

        denominator *= (i + 1);

        denominator %= M;

    }

    return numerator * POW_MOD(denominator, M - 2, M) % M;

}



//confirmation

//--------------------------------------------



//clear memory

#define CLR(arr, d) memset((arr), (d),sizeof(arr))



//debug

#define dump(x)  cerr << #x << " = " << (x) << endl;

#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " "  << endl;





//2019-04-14

//~~~~~~~~~~~~~~~~~~~~~_(＾～＾ ｣ ∠)_~~~~~~~~~~~~~~~~~~~~~







int main() {



    int N;

    cin >> N;



    int ans = 0;



    for (int i = 1; i <= N; i++) {

        string s = toString(i);

        if(s.size() % 2){

            ans++;

        }

    }



    cout << ans << endl;



}
















































































// Optimized solution to the same problem (faster):
//include

//------------------------------------------

#include <vector>

#include <list>

#include <map>

#include <unordered_map>

#include <climits>

#include <set>

#include <unordered_set>

#include <deque>

#include <stack>

#include <bitset>

#include <algorithm>

#include <functional>

#include <numeric>

#include <utility>

#include <sstream>

#include <iostream>

#include <fstream>

#include <iomanip>

#include <cstdio>

#include <cmath>

#include <cstdlib>

#include <cctype>

#include <string>

#include <cstring>

#include <ctime>

#include <queue>

#include <random>

#include <complex>

#include <regex>

#include <locale>

#include <random>

#include <type_traits>

#include <chrono>



using namespace std;



#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}

#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}



using LL = long long;



int main() {



    int N;

    cin >> N;



    int ans = 0;

    for (int i = 1; i <= N; i++) {

        int cnt = 0;

        int d = i;

        while(d){

            d /= 10;

            cnt++;

        }

        if(cnt % 2)ans++;

    }



    cout << ans << endl;



}








































































// Fastest known solution for this problem: