import subprocess
import gzip, base64, os
import stat

gz = b'H4sIAPH7hl0C/719DWBTRbbwTfoX/pqgiBVQilYoIqWBAq1/pNDAjaSAtBRUMJQ0pcW2qc0NPy4obluXayyyPp/L83N9vH27rs/9Y13XRVahFaH4D7IiiEJhUW+o/KgIVcR858zMTefe3FtB970onZxzz8yZc+bMmTMzNzP3u71TrRaLoH6swi0CQn8e7CKwi+HX+OMkgMsXesHfocIQIRXgFI7OJbg0aRcrWk1tjC4J/iXDv3wrhfOtLk06hNGpqYVLUwT+49KkaxYImlQQMuP5sK77GH7fgoWa1JFM8blp2nxWlq+L5eti9GoqWAVNqsqXzP6VMnwpk0tNixhdEUePn1kfSxX4XZxLYXGuS5M2MbomXb7bIF+qcOEfB0tnM35meslm9VdTtR3G1FQvmpA3pqZidE11XXj56OX5E0ZPyMsJBXPGkjo5GO20GXM0esxgdR7AbACfp6c9+NSva99vSNq49sDh/9j94cZ+/VbjswKWD5ukuc5RlTysl9Ui5AmroWh8dhP8K4R/z3047r3eD6zz/dL/8va1tbGda5r9A/9RsqHx4dtdn4/+3HdXeubS3Gz3e97WY8NbB6zvO+WpIfWbVnjufqEn/RyFClxigN9jNcaPsRjjnxOM8Y64hWk/Q03w76QYl7PKBP+GCd8WE3ox1RifZoKfa4L/WbIxvtqE73CTcvJN9PxXE/wVJuWMM9HnYpNyqk3K+cKEfqgJ/UwTvv9m0i4pJvZTasJ3swl9P5P6LDShn2lCf8bE/oeZlPO0Sbu/aILfbFL+fSb6qTbR5ziT+q8w0dsAE/o/mshVa1LPQpNyPjOpf4FJOQdN9COZ4F83qecJk/41wkQP75qU/7ZJPW8wkfdlE77XQDnDhEHCxkV0HMlg+EsY/pR/oWYcGpFC8UIFxc9j+D7JDM/KWc3wv2F8113h0vCdxvSzcJAWPx349odyOlj5qi3dm0zxQmChZnzbb6F8Vy/S0tuZPnN1fGel0HI2LNKWczMrv4PhHezBNCbXwgqdXEz/p3T1F2C8DUkV/lGjcIydIPh8i2uDdb6QVN4g+XyC79alvtmBxdUhKdAwpaY8FAqEBJ+ntNhXEWhg6NLiKTXBukBp+aKaAH1m/MRXL1U1BMorfHcHVvj88E1CpH95ua+yIRDwBZb7A/VSdbBO8N0xoySUB2zrnbk+5BSSGoIr3LOnl5R7/G7yOFgAD6rrQoEGyVPjds8uCZb68MH0Emm8X1pRHwBC5zigWVZdEagDymrJvRQISiTnRJ8P6hFc5lsEVSmvqQn6l9KcIee4yuq6Cl9ldUNI8gUr3bOm+2trKbvxlTXhUJVaxAS+CH95SCIlwINxDeE6qboWhGloCDYUObkMQRAiUF6rVtoPWKe/qrzBJzWUV0shqC9IASUsKg9V+1VqT6mvNNfnLpngmzW9ZJyvhumLMCclF4CWa6vrQJW0CqEpTtRTiNS7tBQKLOgusLpuMSvWgDvRLVWulF8dDIFsoUCeBxTHxAD8BFBWeU2gG6ETmDGP1wQUyDcaomo1GInVDvgZamS8vyZQ3uCGJ2N9HqgT/JOI2YDoY3PVVgiGsbl8DeV1iwPAUm3NCaQ1wWYlX11Q26D4eCLX2LrnpR6oGW+PiNDJyppiEZh6HdiA5K/i7BbqVuIL1NZLK6Av1ENnCjaULw64mYU6x1OpaZMsCleat8c4oEFl+xYvX+6rDzSEgnXlNdVQ7NJcpsB4NYvGslYJgbKKfaC4u31QYoWKnVBeXx+oqyBCAqaiZtZSaAqpAGQnWpRQzrKLqh1phzw/6D8xL5iZSV7MVreslmSeyLhzuisA1VHv4K6t1RhL3CypqET/pAMDrc59BMfVhyW3n1npxfUBsFJsbWJwM0FltcGKAJFvBrgjYLq8fFH1UieaX6ja50ef6EOPAz27MujmnZcTJGH9s4YJnaBxIJ7YEACXsBTENep9U1hnm863dd6yqnJJ37Cs62HDolOvpf4cvi32Q4sg5BR8c+qWodnPDoTCtQF86KdklUEoQwDVSMEaoTIQrBQqFwekEGJq4AFTthRYXi0JtYFaf209SepXCJX+mmAoINSSlkBkbXApOnYsmw0jteXVdQI6eWHalCm+cTm5wjSvZ/IU39gcZ17869ic8cKUefMKJ3t8zpxxFD1vHlDn5TidGrCAh+gcEP9LEtTvyfAvhfxnJd/oX4F9T4nnwO9J7LkVZpFWtuqA+FRGncqeprHUxlEn/pcK47NF6EjpnofNGr6iD84061LVea5VOM+e58K/x37+eCrO7pemUlx4UHUvrMMDcfpkMuar8cyeP92dgjPeFkZf3vULK8581zNYvn+kFWfAv2WwNPJRG8r7V1Zel4/GBan69Q4WR6Sw+a/6Wc3hCzn8Bg4/hcNv5PAFHL6DwxdxeDVeQ/wNfH0quvE38vMNDu/my+fwk/hyAt14PvLJWEjxaVxMReIxDm/l8NkcPonD53L4ZH6eyeF5Pbs4fBo/T+bwNj7+4/C9OPw8Dt+b1w+H78Phqzh8Xw5fz+H7cfjlHD6dtwcOb+fwazi8g8Ov4/D9Ofx6Ds/H+Rs4/KUc/hkOP5m3Nw5/GYffxOEHcvhWDn85h9/J4TM4/C4OP4jD7+PwN/N2yOEHc3iFww/h7Z/DX8nhuzj8Vbw9l3fjh3JoG4fn57MODj+Mt38OfzVv/xz+Gt7+OXwWb/8c/lre/jn8cN7+OfwtvP1z+Gze/jn8SN7+Ofx1vP1z+FG8/XP463n75/Cjefvn8Dm8/XP4Mbz9c/ipvP1z+Fze/jm8k7d/Dj+Wt38OP463fw6fx9s/hx/P2z+Hn8DbP4efyNs/h8/n26vxM5sYSeknZgpic6uUotxJkK/attHnsfFWeBS7Nhn+2oe64BvCVfgo2hGDz7XfTAMYXW90F4G/QBhdbrSVwMcQRlcb3UjgIwiji41uIPAHCKNrja4j8LsI47AWXU3g1xHGakfrCfwKwuhaowsJvBlhdKnRWQR+DmF0pVEXgZ9FGF1oNJfAv0IYXWc0k8BPIIwuM+og8KMIo6uMCgR+CGF0kdFT3yH8U4QdRH4C34twfyI/gRsQvoTIT+AlCF9K5CfwIoQHEPkJfAfClxH5CTwb4YFEfgLfivDlRH4CT0Y4g8hP4BsQvoLIT+CxCA8i8hP4OoQHE/kJfDXCQ4j8BB6E8JVEfgJfgvBVRH4C90Z4KJH/PMJWhDOJ/AT+ZirAw4j8BP4C4auJ/AQ+hvA1RH4CH0E4i8hP4A8QvpbIT+B3ER5O5Cfw6wiPIPIT+BWEs4n8BN6M8EgiP4GfQ/g6Ij+Bn0V4FJGfwL9C+HoiP4GfQHg0kZ/AjyKcQ+Qn8EMIjyHyf0vaH+FcIj+B70XYSeQncAPCY4n8BF6C8DgiP4EXIZxH5CfwHQiPJ/ITeDbCE4j8BL4V4YlEfoBnbU2GSEj5Cr5uxTWmLQhu7oDerRRCdedtcx73yLvvEuUjYuPRU7NKPe2tp0pcgtjetpok7RuGuATlE8h+2j4UArhNJyHrHHG0AonY2JUuyh8vsy7Yton4BnAIpxdsxUexDvtQsgS1SeHo27qSgF6UXxHbjk0SLbvE3V1hyLyZZn4XMovyDpr/CMu/+uZnwX8I4f5zIKdyHwi4YEfKLwBl+XIb+hex8eblhUAgXRWvwoA5W08tAG7yx7FdC6I/gSz2oUI0RNM5hXMLywrnFJaWiA98hm5nK3aNLRguKpkgpShvczvPiM0HpGyx5bGsnfgwuRT4yIcUbC+xfYoNnRekJNzxyAe5Eg6ewxK2i83HpSmYfRc++TPJflL5OcnuJtnE9qasDapLlX+ftZHg3Db0g+1FWWTE6MzUUMH3jarzt8hA4zzulZ/PQrGLm89IyZ7YVJtXlrJcXH1mnGMSxVCi0WLLw1n78CFKsLk34X1Ikc8ZiXXIK7+U1QpfvZEwkNVk5bsfyuGK/vIbIiqHOQwYj/yq80Bx81Epr9D+wvbGrjnhJE9sB6qiA4uSP/XKZ5Q1wNADUhKO+IWw9Mr/9Eag+p7ILWJknOIn5bsFrHhvMTbdZm+a35cqiVaUKRKUt4HUcmVWvti4CqLTprvB++5oynoGQ/wIKKqpNXyNJzbTFr7SE0kTW5YrL+KsQSx4x958fT9kHFN+83UshloEuhmELlVLd29fpDurrAI6seWlrHXIuuV5wlpZfzUCL2WtZ0h8qIwDF7s1O66cVyEjaYZWaZh9bqu9P0jgYqbgyqASuTKp6tu98sqsbDHSREuMZIgRl02EJneJBdvsTZcBdaV9aBMznkNKvhPT7Z7IXJvnxrkOaTD2Jehp14mNr9g88lxbdKtAskD/LY5MFOVd3pGnsDN65O0vImuvvSjqsWy3P9rqlaNiW/Rm+7+32drETTH6Geq1u5Xi5uOFL5GdhOHdDzwF25ctu7XlpuMk1HWcIwYALLAq3pFfeOT3PW0xqMkusbGjy2vpwFplFzfHpD7MFF4GtUxvqfnWhsq3oYYHd8Vi2JjZxfIIjxy0TW9J/swjT3OIjdtsYsH8LJe92QasOy/xyueUu8BIoisBjBb07W4DZdoYVNuTtJXAfsag/YRHipEkbau+25sq8LdnsQc0EXrSBJE0byR7a2a89VK7iLE7W7FnZ8cF/tNZaqM73DZikMwwM2jDKNhkmdh8LSuz5sWtZUkm1nRl1kKxRcqap/S5HC2LtHcR4OSmrHlWLAUAWkxRVhVaTbIYc4EhZOOTevqkJmu5N1Jvw5qjr8QWQY+wRqCqwHKUm3IYN2VsDu0l81D/BaQ/jEvoDyd60f7w72dQI0VZZNtEjBBOtGRvwVf2pu2kx1Vk1XfOFBtbu16krvc16YoXsRKn7G02+WHCP0KTzrSIreW2mOxofu3+IGpiIdZtFqivc2ElfnJUe/ZGVhF1iFhL8GnTwCgqsmahCKIyE0WQD4ttX0/yDot6LYeBSJST35CuJ+IMTxDHR1QSU3Z8RcURSevGXhUbt9s8BSfCP8dyq5TLR6OQRdgGROEurun7nDFs+ue/+t6mh9bKhV7jkT+87x5nK3yTemH3ajxska7yRJKzRLmNSSJa2sT25LfJeEl8YuN5a8PNpL96In1fFeXXxbZvgPCYaHkd5N3riXhftWmxLaJFlPvuhdaweguU8E4RRoJcToyirwzFOH76e8VweCP5XEHnTmMn3+F8DXtsd0G/JujUwh1TbeDSpzqoa5+aQT3752KkABXsQnt1k7z2tddbkIc3ywYxR4yMzuifml/zyjvvq+j2bziakrHdY5/RKraUpgDuhNj23SSxxZsCld8ptinwvcgRg3BCbPw6tpkSe98TLa94IgPenx4Z8qZ32AnRckIs+GDVVR55wFkgs9z/6+mR5Dc9clqnnbM/jzzkbHHL7RZWj/k/kr+o53/fVaKGv6jjLwL/uKaKC74slvfbH/4UAutOG9GV23kAbEk+XAzdcG0RTJPczneL5X3ceFCUlV9s2Vssn/a0fTupeNhnxZbTxc3g2FvvAyJenxDjodpF+4y2H6jWw91qvTyu1l+CWIeLZaJZ2zqiTwBirUQqHMm8ll1gQB5gVTzshMeyo7j5gFfe5414s3Lv8/9r6sfUfrpb7ZeLfP1Oo9ozSPwI9etM79Z/sZx3Ft0I3zeLCwa8Zm/5FQm0WotbXDHpI9UgtnstrcWRvHZPY5dlS7z/3vci1x7bxLZzUFCnaNlGe2m827aUWi2eyJBDnsj174sFnfdd6i340r723hj2JKjVAKwfutu1iwnq+rMotQzRVJFg8Ra0rvzv6Ax4oPWfnti2KFYu7k9BnuhvCYLE06Ds4pY7Y/YmfHGEkwL0j1Kc46XYRuyl5/qLUH+R1n8V1n/VWqLRjDh/qH/LMmxGff33Qf3vSqi/aKT7h6diAWAg0CvusU0vSP5HeATEBQM1lNBqnhuT34S+YX+stbOvKq982NlaZH+hw5tUkZXvib3ilRWIfjwF8KXD/vBbEJN3JrmdRz0tS2OkK3V6Ym+8KLCIMvu+gCfS39PYBv3uXWerRz7laenb5jzD99f3wNg+FwveWzVAxEh3SK634MBKpXM4jbdA2FwQdodX3mH/ZZv9hdc8ltdBdsJh5Z86U0X5c3gkFnxu/2Wr/YVW6BskIhNHtjmPi7Gdot0TxY5jwxAgS4yJjvBVIoyM/VcvtwnhPtA6ygcnUbn7RLldOXQC1QQuG6lHEOphYiRfl+F/ujP8kWXI6DHD8u4MqyCDJ7a9eORXxSM/9liOb8X1fa98QikiJaV8lJ8JTehSxMj6Xf6FGHzZm3YnwzTuJ/mClPLQlCmdV2DAVUaok4AydwubhsR22becIsUpts+RX7vSinwj8yGGghhuGMRwjvBgMXIj1q7P6p9A7VKUj7AgKPDj4xi/x6TBEAhkhC/zRCYhVYry1nEaAGw/TuN2EoGtuUYQYCB84FWc/91ZOL9wQeFdhb4F23TxIZlShOdg8Q9idggoNwjmMxAi671fAiFOVprr8RutbIry9ElazVugnGgZPuGiJnvTP/DFJuPIiYTuWur2HqifS6De3AP1bxKo/9AD9foE6g09UEfgWTzosz/ywnfYACzwm4tq+DVgOIKnvuAIJiDBw19oCEpOcwSXIUHhaQ0BCXFUgtOfAcHYrzQEl/Is9iCB5Qs0j3MwHKGJDYaWA+OJt9q6Ttpqazqp8ZC5RefVmrmFvakWw3XS5H78pptjNLXotCYtNouR50A1wIbtTU8SPz4TSnyUTkb4EqV6TWm3mpWW3x1x94sLfZBJ9MIx7YQn+oyFay0uwx86af9pPsYF0DRoPjIM8qVZ6Owlfyv2BSXnMxyo2rFoBTczoMo4lY7UK2LjjgGoQ4XMz45RhSKw5S+lLmEzrncqu6LdaBGXApQcaGZuheH+Y2Q5A9Xe3IbRY4TycR6IHrRg7LYjekig6e3fYcXBg2PbwvxlHsa988VYsS1cJkbcgraRjlv0pr3NYm7a+G6fMgUqG732HMelcWVWpiCNRX+aSVzpCPqV+lMHAYhTTVGGoyDgXjKV61FmyJktSCPoFCQmZoSHsNlIPjXEtCglz1bOK5wfa72KLkps6iQhuaoNrWg/S9LZ3xIzi5kHZRA9o4XkQQ2juCNJlpS6n5xUBuGTx9OImgkSpvJKCiDjFF2omqFJmv6Pm6fd/R8JTli7G1CUk3ib0a9GbSJIvhPUakSaZibSeCOb3o86hGr++VNujhu9mXdHHPXvFFysSttV5iKT6i40RmLrl5A2HAV2FR6NcnQRq4Whr+WlZPweeT4Z13Ua37Yoi0HezmvQLNPInOek4mbtSDJBXCu/ovxKod4Jt6Xx0SlksiCq6QD3fUpXWJqP2psHsQ6AdBDARAtoD4BBuCsXBmFZrVE/i5ONyfLDpGKoaWTigLEWCxAtWpuRJl30nL5bXSs/pZ4FGdSTVnspKx/7yzWsc89C4Myn1K2kg8yuv1qIH90vqH70HcHAjyaObGvMR5/OpapmPDJMtNvpd+KOEtYdE4zL3nQ2gddbPYx0mwRj33nPJ9TZej4GIZuO4/JWTLkeJY/QlVXi7DdZVWf/R2uis/8xTfH5x1TJrx2lTdKqOnu31bjCrR+TGO7FHI35vJLzf2g+N39sYj5HP+HM529Axa2tVh3l1jZmkNVVdzw824pbf0r4E7aa3CLCPLqYBMj9vHImLlWneGIYYMvFNlz5YKFdJlsB8cjTbNjdmo6QQRlm4Pbm98moDHalMZoXE4zmkR4MdBXpqqsE6uCH/5Nzny8exVgWWH7wLQbbhOU7+DWB5fNWPcuHrOZ2GjZp9tf+iXbyqfJfR4inE+a6hC0bwN1tbp3tIouBO4l+a2D6xA0Qlx6lIfEmtsa6hKyxVuj67Y8yhtx/0g5kO0KNYpO6FQJsN/7vsX3xCGX788OU7UaOLQv0ca4EbIfFQ8XtrKoLWB5114ZtPyzB8TwfhnZb2Ee/Rv51fabXERod5CuHOmgw4RIkkS63IMeb2cqLluM0DcdhZhztGGDM/afx2PjIYcrZpQQ60IbOKqP/SVcHj0ezvzHOc+dham3jIEe062v9/J/bn2v8rMojnxHl89wAuKqDRIDO17ARrhVbSrMWbvl/bHvOeThxH0uU9+OyWTZXxA0dbE/saLwMV7yM4x1Ge2Efkj2pNLFxuSLYm37NFt8dnkhelhiZoTjfJfJjZNp4Dlz6euIfbvFGJnksh1Qisf0VVLFy7iBqiN83+59DTGe4Ktq0lSzaHBdb3JbCl8nQhHs+/6Yuyogj94mW7Vhp0XkGvcWdhwhnb8vdGWLjeUt4VuFDaYVr3DCdIHV0HkcDrRVj08DDne+s4Pg6ISc+bpVmiO0s7nIxydnWlLy9c6xXPumVvxPlY8o6UPCmDlalZnsKrq7keNqnsvF0KtvG+wqcF86dHdK1xHuFr0rwXM3BZLIbqIw+qPHkTwGIbdvqkT/DdX/b922WiXKbR7Y7D+DOYTaul3kiE1DbULYof6CkE+VsJ/wL5in2n9ZhGCpHxZH7cRIzyyt/gmSLOzRRVsZBdZoh5WLfmUXCU0hNY9NOe/f6FdA5DxB3qRUZ3W9xZExxJGwrvjEMysEF9BSPfJXzgKdxh61YDtuiDqDRrYfJ87NyPZEFoK1T2PZk165d3bX72mNpJ7t2Xxvv2nVBiPEy2bQbxW/atdt/1gicbm256TxZvJ+rqmmBgNVjrOQ2sfFwl2iJSnYxUpqVK8r9oW2gN+XiOmXTo2y8E9uUJDHWCkQkgwXVK3+Am5DHpXQx0gcGVlBWEp04ltjEFhhnQTuZYmOXtWEyOp9+YsQqyhax3UqJJgPB2zBhtOGk6V4AVsDIPNlGXz9qteETT8EOUf4cwubwFk/L1C663SJ/1DnL2xKwRZ/Uz7kv7XZv3qz5EfjHu9Kb6U5c24cQpTsr9ftRAQGDhJHUlK/Wm3L4F2jGlQfI1j57Q4ruLW2nC2ugyMaOLpyCZnpbKrIdoGDcr8d1rVy64znyAPb/WuhMAdutLUXnweG4HaQD4RabDcwQc+cTE5eGkoHnCt14F74DnVfHB+j+z0OctMBib/4CQobo7y5KE/ZH7jyPYRZq4y9Qq6j3vHap6vuyL42p2SXMvphsv4EMOEd24Ewye+tTpfg+CdQ0KkEFlSdB6dEQsImWWASi6WFU04MSNO1DTX+7n27UDyUb9VfoNurD81Gh+/Yj2y6x8dUqfnWPl6MuUY5FGoK7Ewl8GoKqRIL58UFn1EMp/3ZNprCmaFRGdN83mkWo1HOqim5DJZzVPr0irsBx+LR3TPN0aPzpZfjUEaPrpF2XojPVqBk99z34pwY3VCAkyBWkcjTIXBISlNGvupBgwkX0md60Hi37aQSQq/j30W8O5TU72tzKLBtjaetmafsXsBzEWNqUU+/TXYFszFsvxjw2DLTAAb3xY3m8sI+Gc2vfp0sFZR8QBxkPfgfup/hbdPjvIF+0mjVL+SVoCu3K7STdztZKzir797H4Ht83ZPH9+FhifP9DKn7+fRpdvbcXKoLvG2red7KRVZuvRPmmrMLVq2wQy+xPxlBllWPLauiWzndfRA+s7EOpG7sgkpmYonlBKraXDc/SINOIoU0kW9s2tzPW2atyneeBdgHfe1JHn/s9Lclp4s2xJCwTmBfavWc9uB4XceCI7FAOAA/gYG/6qaDh3bhXHZTpgAYmfghlduDLRUoqVNv5vlH89xGpTyRflE8oh7BZYVi6jqwDZiWsAza/yZZnHn8P4lK2/451y1eeh8KhVs0FZNUqOcsbySUrm1UKFPh3wso+46PG5V3C8j7YyKX7sEFTsUfCkOe9MvbQEBsnzV/fU18UYy/VjLJv2UNeywL2+JrWKZTo5HtkWNFsN0BkVCyf5Ipa8p5OMVuepMEsKqYLi8nYa6gYT+QmUMFcBV/wKm6pUzw3lilhO76V89u9RNjHtnVaIZQBhWUQhV1Cgj9PwfbwPFTSPf8gdiylERuWLms6UAwR5mjdfqTOqIEkPJnE/5C76QAOczZ7014cAA6SNx92dMVf5KsiRnOq0N6WKjdlJYPxRmjSOVfTMyr5yQsho0lnqYZsoRnZjMJIaosYK5TTQehHhpFB6yRZioOnyrNQ0WhfrSO+McbW6pBARoKRWoK/necIqpDgN4hBZTzwKnZDbmAiuw/H7U27yAJYMXiDHSSQ1C9ST0qY7V+mm+1zQkXxVyxQMlloUJcWOu/mZ/C3sfa7kw64pYnrC18kLIvvtJhz/Iule00Yy/98D5M4koGhdDWJXPwXMVPn20g/8yWKte+hbvrT3YxTO9vzPqv8GoSjexJP7KH9oz1JXcPNTFbXcGf8g64qEYwfNyLwRWfl8j209bKT6VJsBqTKu3s0k4Qvd5OtDlzDa76TLWUjHfi96DJ8r5QwuDKB+ZoUlfnuPZQ5wTQi88tJfd+lzNelUOarIVXmaJkv5ZhPY8yRDpn7E5d5iLKO7KZj1uZdYI0ViavdhOjl3XT8+HckmoSvnZDdlEXxteUnB9HFQdSYGOn3m0Hdi4ME1d5EtKYuDtYn6/cj/pywTPYzwdSmOsOU63DGFVUFXMdwXAkKt7JSurnuS9EtSd6vMbLbzbhNM1LJs7vokg6KpS5JLkSDuO1d2n7LEcgCxXXeYpR/CcuPFVTz78Q27c/y488GlaO7qCl/y9Lk3XRB5UNi2tS0PHIaFoRf6VL2NDbznma2kP2nBGU396DskGpGjBF+vUBGbyZ4il/14ClaLMYmOukdsgCdn6GxscKMi7OxH+VSXnrbpLX9u7jWnvCOZtni07e4BehiwwXo0+8kLkD39cr58dccTdafRXmKjewTVMT3Ce5I3CewN92cMDhc2sPg8B1wiT5g0govvkVa4bmBmj7394EX2ed+TCtMeMukz3z0NtdnNr6laYXyN7+3Fere/pGt0NeitoLVYtAKHyf0t7+b97fo0wLzquo2wNA3uG2A594kr7RAofhaNeF5AL/peT6bwHN1D328zkjd7W/QnaL/fB3VnpSLOwCn5riEzuuNqP+DUd9DqbX7Bei71r9pPLgsZBnzIWPUfo78HqOwDBd6Mzzyd57IXeRFn1EkTrg24WXtZ9nb7t+8htsUU+m78pG7MnrK8wuWZwfNk8HyOHrK08TyPErz0KA7chVmuZpkGRJf9X/nDeqsFxPSVLr682rGnYV3aVcb5vBTt2SYuiV3ejQEt/EEfYGgb6dbQzCDJxgABAM6J3Ph5lHydk1elnIeahLdq32z5tx3dNXAphzCp59pn/ZnawoOpQ2fWukbeQbr8bOgjYojtxCTfIa+oZJhb36KaGeoJxK0iQWd0tLCl1CRnfnmU1cqP9ftR5CaTwHunUPWeSOj8E3pqz044RjiYUGwt+DT8B8gKFfOt1ObI5rGHwR8FH4L2GPj2LAlPmqnJvZeO98iNi7artTvN5ThzHg1CXC+I1O6DDRY/IVi/BcyZ3cC14InCVLqCxE8kkMrL9gmtszPspFwDuliIMMWO0ZyIxnmrZ1kGkhDYPpah42+JLAy2RaRkrPx9QARRc9A8hxk1IJTRvkgvhOwFuAdTVnLgN0IioeqIYTHdQlKcKca5P51J30FhE6Ib8pSsl6jO+ugWgwjAu241r8Ff6W/GY8yQtznO2lsGklpd2SSF4ehav32OFQ/70224aq3g3r4IvwJw4W595UW4m8wSXDvy3H/dm47ffPCQX07vtqf/BqVfKHyQTvtVEdo9ToXkDrqlkZ+DPf9O8h+vL3JGqMx1nrgGP3qO+KPSkT5XDxa/4lN+Zb8JuzQnVF/u+HzD+lzpaid0d25HTtQ3L709L9n9ANU+lE9069k9Ed3MPpzrwJ9nHzdLGUJlKS4d7D356G7yrHCMo98pnCOR36vsNTbcq2rd6YwR2wZLUJa4h35Mczp284n4S95ldGv0hWRq7rfFz7mlc8UQRmxAR9CF7NArw4fI31ogdqJtnH1/XIb+00w+wkwnnMxpiKwdExIqqiuE6rrlpbXVFdk1lRLgYbymszKYENmTbBucfbIzGXVUlUmnneS6cy9YYTAnz5zww14GEywDqCwX8qsC9fUZNYFpUxSluAZMzMzWA/F4ZEomfA/OYmkIrOyuiYgNIwSpkKaOQxJ6gg/PHwKChUye+uYhMKL4KswJRiuqagbIbEcmLv7984znGN907wzJxd6fb4ZPmd+/QqpKlhX7R+PZ7+EnLll5TXhgBtPBnJfCP24Eqm8rgKP52FZeqYvcKtHv7gvrD7jJoNC+UwOdj7Gwjkuzbkb8XMC2PNc9nzdHJfhc4HhN5o831VK8bt0z3uu70TPTE53FyDfBHfd0uqGYF1toE7S5dTWx1VmXB/1uYM9X13mMjyvU9UDxjTkfAeW6s+Hi/9+v0xL7yjpmf6UrnyXjt4yOOnGJnbWxqbWWIwsDkFnxdeFqiHFFwzmgevASLWrIxbD92LEY7HYGvJ6VSy2D9I1XbEYnpNb9XUslgv5lkPIhZv66yGth3QnpGsg7YJ0A6T54Gt2QfoMpBnssJMB6jm5984WLMsdlsF902zrLGmOAew8i7ZtsRh/DoMxPT07Auk7tsZi67DsdMfU9Ixb7X2W2VYLkwbdeN24rKv583mT7p3lJSWkJeHRdUlqOXnsHIp80MGjgwUheeUdLqEw3TE5PWNyeubk9OzJ6bmF6fnT0jekNKY9nNqSsjb5kaQHrSTffGynQ6CrXpBv451G+YrSN1gS8j1Gfscci/2yL+SbP9+YX2u6Jt+AuBxaPQxhMtq+isUew0F8crqjMD2jKD23MWmtlcqH5/CsgTbcTQ6GTOBVmO7SsCIf1MlNUF7u2VisH54MlLdArWdheiaoI6kxeS1QY71wezQDbOJKVj7uBSP+eTwHBPDX6vBvor4N8EfxnA4D/LdY/7ZYbBjDq+cSD4HnC4E+IFC5H7G60zPWJrnTM1uS3enZD6eI6bkPporp+Y1pxemuGpQU5M0msoMGQBYbKR+nwmugHKuuT8WS/vjT1ULS76yj2KEwQ/C14iUMcCJwnh3nko8HIIQt9KyZ6fhnipWSfYhHM8xjwFEEsEuQY1ZRED/Y7uL44ZlJ9NCe95O4EzZn458Hk2nX/QwL+FsKPavnSSxgZj9BKFfJNgLwpnqs0Mr+9GiOffhEvISeH0TIiuHPSfW0opsGUD4/QVVIA+ixRwcR+Av8uUUt7fPLKVMZJz3Dr6B5/IOZ7HdY4zr7zQOrQWlPWkazE3meQInuYcBzNmYXWFQ7AJb9zCm9g8Bwdjrm+0iG7+nZ1VriqmQ6O//aUm2lhwPl47EcElPabQjsBhmxKbwInEyhMn+Nf07Dn/lJmtO6Y0l7HhCSdhHgA7UNPmDNi2+UCL0stOz/Jg3CgPMI/I+Fnu9jRbIvLTSPHQH8zb1NZeRgx4C6cOpwdQo9M+ZWBGakcAdMqaceT8Yn/8nIWhF4A4C/qaX9tBdV3CD8Y+tDgQ14tsgl8CdiibfBLiFpBjl1W2WAX/BXvjEE2vizkvawA6GewtyH2Kk//21htOkW4X/nUz+EjU/sHPdZQ7TjmsUk3ZuihTt08HkGq2dTdVxOy1XPpDrNxsUrBO154oN1546rZzQp7Lk6jqhnakF4HyTn77Dz0tWzuZ7p5Yqfi0YdNoXVs7Xa2AP1TC31jKjLdPpJ6j6IS3OMuytFOy6qZ3+pZ1BtuMSlwa/v79LU28YU1UvHH2YrRJ4uB6WPMVitxykGL3G4hP/LT/wce91nYAatx3CWTmDpVJaWsbSSpUtZ+iBLH2fp0yx9gaU7WLqXpZ+w9AxLU1k8NZClw1k6gaVTWVrG0kqWLmXpgyx9nKVPs/QFlu5g6V6WfsLSMyxNZefuDmTpcJZOYOlUlpaxtJKlS1n6IEsfZ+nTLH2BpTtYupeln7D0DEtTWX8dyNLhLJ3A0qksLWNpJUuXsvTBwcb2M23KlBsys+csCtdJ4cy8nPycvNFjwwRy3ufMy8nNy8kbSfECI/LXlNctzlwaaAjhtG1czvic3NF5NMvY+2CiF5JWjM3MlsoXh8bMdnvdhSVu37jxuWMq8RjNkZnZOFOswNme11tWTLOPFISc0IpaqXwRpFIDTavUb9V1MOWsF3Jg4hjIKZzsGQ1FM2hxXThnUbi6pmI0TCcJVFUeqhJyKlbUQXk0hYkhecIqrAF88KwhUFOOhOxbfY2ELKvhrxRYDn+h3tXwLFhRLpULOYEqX2VDeW3AV1XR0A1BoX4/O8LUJ5HjkkkZvvKGhvIVtAz1+xJ/A6lYeW21H/IFJfKH8qU8FoVCQo4/WItzox/djwczH22Nn5/vip+jL+jOshN0ZykK7Aw5/izF7vsqBM351+onWQc7dfklll/i4t2e8mO8CSF0UM2v+v31DFGhnpOvGyfi81Dm8626cUF1sM+wcSGVyW7T+ecyRmrVjTPP9NKOK2b6u4v5dDW/6seXsAFvra7+umtDhLvZGKHC6jjRxfKrL6insnrq5b+X6dSqG5fW99eOS3r9qfI36fKr49yGS7TjYgob+/X51wrdd6zwcUHH5drx3qz9ZV1+gY0HKoN1Sbp1A136mC6/GvesY4HHonzj/OrnCV1+NY45XaIdz83qv0HX/wS2viKUsh8jJPXM/xld/u57X7rbpyf+L+jy72L5d7H8v9dNvvT206rLj9N0mrJ4L6ln/u+y80eTdHGfeq+MXl49/4NsmpKkiwuVBcb0evgYq388nmL5T11g/pNc3+LjIvXeH1Uxqbr8qlxdOv7q+b1dvp75q+l5XX41LhVYss/Sc/5Uizb/PnYe5L7yC9N/Xzb5StKdM6yw/DZd++vHg/6Mf64Or+Z/0GT8UdP+uvN61U/dIuY/LD37X4vuHOD4+Zd3s/NP2SG4ePBhsYH/6mXCf/m9NH28f8/8e/okAbU6Hmvx1vg4q8UnxcdPLT45Pi5q8Snd450Gnxofx7T4NMN5RhJopcsQ3ys+nmjxvePjhBbfJ+7/tfi+3X5dg+8X99dafHrcD2vx9m7/qsE74n5Ti+8f94da/CVxP6fFXxr3X1r8gLhf0uIvi/sbLX6g4fwqCWaTqn/Q4jO6+70Gf0W8P2vx3feiaPGDE3AW4rM/j+nx9CzdRD1MYnhcduU/tzE8LqvyHz/D4zIm/wmTftndvsM08cIgIUV378rLjF5dX1fPKj7B8Oq6voq/2kLx6rq8ejZzGcPnzqD4xxiD1Qzv0JX/B4bfNZPid6t6s7L65LN1FBYIPMnw6wop/pdsQaQwieI3zmLrIswp1SRReZN18v6E4O3x/QXVH/2O4dfp8AcZfpcO3z+Z4tX9ERU/jeE36PAhht+oK+e/GF7dH1LPYN7N8Oq+lHqmcnIKxQs6/ESGV/d11DOSaxle3c9Rz5D+D4ZX97XUPYp2hs+cq6U/y/CtunKuS2X61OHLUo3tv5zQJ/ZfvAeA2JvOLzUyvEO3nvY4w+vX2X6fStvdomv3vxN8oj85wsqp15VzgtAn+iUzufrhOi74veW6fj04zVhewcQ/jCD0iX7pZrIAdmlC/WcwvL6e5aScRH+4JA1jiUT/Fk4zvlfqMRN8K8H3E06xfh2Pgxn+z7p2fD/N+F6pgTbj8m80wfttxveSNZjgHzQp5wkT/N9M8ArBJ46PJ0zoL+1lcj+YCf4GE/ztJvhmE/zTJvhWE3zUBD+gN/h6K/QLJq+6vjuqt/E9XXW9jct5oLfx/V1P9zZur1d6Y2zaHW+o857dJuWfMsFb+5jcG2mCn9LHuD4L+mAsn9hflpiU83gf43vS/m5Cf7SP8T1mvfsa3+c2GvD9rVcIiq4+eL6rof30Nb4Prd6EvoWV36Er/wkT+j/2pf19NbOTAMNvMaEf3M8Yn9vP+J66GSb09f2QZlCCHlaa0P+in/F9d2+a0H9mgu+fbowfa4IvSTe2q6p043vz1pqU8ysTfKcJ/rwJ/jI71ZstoNXbILsxvc8EH7Ib36f3BxP6PXbj+wCtDmP6TAftd/r2HeEwvq9PNCnnKRP8n03wb5ngPzbBJ/U3vs/wyv7G9BNM8Leb4GtM8JH+tN9tYHHLo2wKso7gDeaDYxqCQWlM/YpyyR+sCDSMqW8ILqoJ1IbGlC/2547LHzN5DF5HNTbHX19PrqPiV91zEzDOBMzYBMwEIf6mUii8yOfxdTPw3WH2HpPT6fPh1oNUXefzefNmBOvo/XAX/JpZUS69AOxi3gP7QXnGXkCePHxb7oIo1Te9vq8qYam6BuQNVZU3BCp8DYFKT4k0YWnALwUbPDNKcn20NHI/Xkm5p2S8z+12qxWYfiE6x6wTK8N1WOL4UH1NteSv8dyqKxoLLfXXhBrMy3DTzKF6JANEhXtiZbBhWXlDhafU566sJxWrn1mS77vgqhFtqnXLx9cWa6rrAli92d31I0TfV0FKFC/ieytZ0GMluxXjX1rD7rb05vt81UGy4YX3JF7Ma5IXQK9/jfFCsujerLyALAYvE35/ru5XFr+ftkArQslFaqnk4rVUcvFaKvlBWiq5CC2VXJSWyi5SS2UXr6WyC628v0EKSeHKyhy/4PPdOmW2z+spKfX5hO5bcH1Src+Pt92GBAOUz1cR9C2uCS4qr/FVQKcO+crDywV/sLa+JiAFKnImFOSPNSbyde/9+kDxDSsEun9cEa6tXQFZOMjXvWXMSH2+qbMLi90+94wivMuX1Jx9Z1LPnDq1xF3qKy2c7HUjhaaICi2CXOYo+Ipun1FY7Jki4GazitNfMOpy8Vc09nwhq46WXhzpD4WJ5EKcw0XeTaqvgeG1vQnVNLxYWEOVU3BBVySTazgTi+cu+zRQUQ93F2vr4HQKTDvGF4Zqy6ZXczIcu2mT3PepRSVc2al73OMNrXppEu461bdy932iiWxM7hVObFLTO4ATuOE7J9DmNTW++I3JP+yGZG3J5JJUAwESb1DW1ajHK7Rn+siPJnzhUKAi8eZkXQ0aAoGECvR0v7E2O73fVVdAD3d46zu96TXdRuadcIGtoZswuoXboCcZ3LGrpzK4tllvGCCe6hETLq1OtDdy13EimruFW19+RSjoq4KRFpRHL9c17HPo7VgI9S+8LVzvt9jdvHpr0d52rZcu8Z5ovYiLQiHOIuJXpSc0xgXdn+xycXcAJ976bOhFEq6ATixEe022USnaO+i1JRjeXG9y4bvO9ZKrkg0cxA+7+FzX9QPBSr05xa+H10pAxvIfdvm4jif5jVWCCV3w3d8Gw/JEflgmjbnUrLub3Ktu1J7cxew6VZCX5IxuVE80m3/BzeEGA6OBdGyES3B0muu64Rm7PptUbgKaPcy6EwcX7mJ1gwiHXo1uUAn9vfGJply/orvlnXmJ14/r447qOoH6tf8PzdGB5A6MAAA='
bin = gzip.decompress(base64.b64decode(gz))
p = os.path.dirname(__file__)
pymain = os.path.join(p, "a.out")
with open(pymain, "wb") as f:
    f.write(bin)
os.chmod(pymain, stat.S_IRUSR | stat.S_IWUSR | stat.S_IXUSR)
if p == "":
    pymain = "./" + pymain
subprocess.call(pymain)


# compiled by pythran
'''
#pythran export main2()
import numpy as np
i8 = np.int64
i4 = np.int32


def maxpush(val, que, sz):
    i = sz
    while i > 0:
        parent = (i - 1) // 2
        if que[parent] < val:
            que[i] = que[parent]
            i = parent
        else:
            que[i] = val
            break
    else:
        que[0] = val


def maxpop(que, sz):
    if sz == 0:
        return -1
    ret = que[0]
    sz -= 1
    val = que[sz]
    i = 0
    while True:
        child = 2 * i + 1
        if child >= sz:
            que[i] = val
            break
        if que[child] > que[child + 1]:
            if que[child] > val:
                que[i] = que[child]
                i = child
            else:
                que[i] = val
                break
        else:
            if que[child + 1] > val:
                que[i] = que[child + 1]
                i = child + 1
            else:
                que[i] = val
                break
    return ret


def minpush(val, que, sz):
    i = sz
    while i > 0:
        parent = (i - 1) // 2
        if que[parent] > val:
            que[i] = que[parent]
            i = parent
        else:
            que[i] = val
            break
    else:
        que[0] = val


def minpop(que, sz):
    if sz == 0:
        return -1
    ret = que[0]
    sz -= 1
    val = que[sz]
    i = 0
    while True:
        child = 2 * i + 1
        if child >= sz:
            que[i] = val
            break
        if que[child] < que[child + 1]:
            if que[child] < val:
                que[i] = que[child]
                i = child
            else:
                que[i] = val
                break
        else:
            if que[child + 1] < val:
                que[i] = que[child + 1]
                i = child + 1
            else:
                que[i] = val
                break
    return ret



def solve(P, K):
    count = 0
    n = P.shape[0]
    p_ind = np.empty(n, i8)
    for i in range(n):
        p_ind[P[i]] = i
    maxque = np.empty(n, i8)
    maxsz = 0
    minque = np.empty(n, i8)
    minsz = 0
    for i in range(K):
        maxpush(P[i], maxque, maxsz)
        maxsz += 1
        minpush(P[i], minque, minsz)
        minsz += 1
    for i in range(n - K):
        maxpush(P[i + K], maxque, maxsz)
        maxsz += 1
        minpush(P[i + K], minque, minsz)
        minsz += 1
        while p_ind[maxque[0]] < i:
            maxpop(maxque, maxsz)
            maxsz -= 1
        while p_ind[minque[0]] < i:
            minpop(minque, minsz)
            minsz -= 1
        # 最初の数字が最小で後側の数字が最大であれば結果は同じ
        if minque[0] == P[i] and maxque[0] == P[i + K]:
            count += 1

    # K個昇順の場合は、元の数列と同じ
    m = 0
    k_conti = 0
    for i in range(n - 1):
        if P[i] < P[i + 1]:
            m += 1
        else:
            if m >= K - 1:
                k_conti += 1
            m = 0
    else:
        if m >= K - 1:
            k_conti += 1

    return n - K + 1 - count - max(k_conti - 1, 0)

def main2():
    stdin = open('/dev/stdin')
    N, K = map(int, stdin.readline().split())
    P = np.empty(N, i8)
    for i, c in enumerate(stdin.readline().split()):
        P[i] = int(c)
    ans = solve(P, K)
    print(ans)
'''


Measured memory_bytes: 24388