#include<bits/stdc++.h>
using namespace std;

/*
MOMMMMMOMOBMMMBMGMBMBMBMMMBM  iivvYuVoqXPPENGGOGMMMOMOBMBkkqMOBGJuPkkVZBkiBBBMONNqEGOOMGOMMMMONoLrrrrrriiii  BBMOGMGOOMOOOMOOOOOMMPjIFSXXBB   irISVJkP
MMOMOMOMOMOMOMOMOGOMMMMMMMMBu   irrLYYukkXSPqGGGZOGMGOGGSokOGOMSLVLuFGMBuJBBGGNNXqNGOOOMGMOONFYriiiiiiii    iBMMGOOOGOGGGMGOGOGOMOJJuFVFFBP   iuLirFkN
OGOOMOMOMOMOMOMOMOGOMOMOMOMMBk  iiivUuoVPXPPEEGGOGOOOGOGOEOMOONoPXINMMBBSZNrvVENGGOOMOMMMGGqIvviiiiiiiiiii  NBBOMOGGMOOGOOOOOGMOBkuoSFXkOMi iYXvivPPNU
OOOOOOGMOOGMOMOOOMOOOMOMOMOBBBS  iiivFoVSqNNPNSOGGOOGMOMMBMMMBYvNGOBGOSoSSvrJqEOOMOMMMMMOGPFLviiiiiiiiii  iVBBMOGOOGGOOOOMGMGOGMGFoIISIEBB ijIiiUEqENu
OOMOMOOGMOMGMOOOOOMOOGMOMMMMBBBo  iiivUUSSNNNXNNOGOEMOOGNGMOBZvJMOGkEXvVNEMMOOMOMOMOMOOMGNNuLriiiiiiii  iJqMBMMOMOONMOMOMGOGOOOONoUoXIPMBNiJr iUVPOZNP
GOOMGOGMGOGMOMGMOOOMOOOMOMOMOMBBo  iiivuUSVNEEEZEOOOGOGMGOOMBSvqOqSPNqEMkGMMMMOMOMOOGOMMZZSLiiiiiiii   jGMSMBMOMOMOMOOOMOOGOGOOOouuFkEGBBIri iqEPGEGEG
OGOGMGMOMOMOMOMOMOMOMMMOMOMOMMMBBS  iiivjUSSZZZZZNGGOGOOMOMMMLuGOqNPNNOMNGMOMOMMMOOOOOMGGXLiiiiiiii iLBBGYrMBOMOMOMOMGMOOGOOMOMXUukqOOMBBr  rNONNGGZGG
OOGOGMOMOMOMMMOMOMOMMMOMMMMMMMMMBBu  iiivuVNqqNGNEZOOOGMOMMBPvUOGZNZNZMBNGMMOMOMOOOOGMOGXjiiiiiii  uBBMIiijBMMMMMOOMOOGOGOOOOMOVjkqGOOOBk  iGONNNZEGOM
MGOGOOMOMOMOMOMOMOMOMMMOMOMMMMMMBBBu  iiirIkqXUqGqGGOOMGOMBBLiEOOGGZZGOMGPBMMOMOMGGZMMMNUrriiii  rBBMurvJvGMMOMGGOMOMOMGOOOOMMqjFPZZOGMMi ikGNNqNqZZZP
GOGMGMOMGMOOOMOMOMGMOMOMOMOMMMOMMBBBU  iiiLFXZuSGENOGOOZGBBG iPMGOGMOOGMOFGMMOGOGGEOOOqXJriiiiiikBELrLUuriOBMMOEGMOMOOOOGOGMOOkXPNEOGOBB  INXNNENENNkq
MOOGOOOOOGOOMGMOMOMGMOMOMOMOMOMMMMBMBu   iiLqEPSOZEZMOMEOBBv iNMMOMOOOOOBVFBMGOGOGMOMGEIYiiiivIGqrrrvvLriLBMMMMGMGMOMOOOOOOOONXkqEMGOOBk iNqNEZNZENkGq
OGOOGMGOOOOMOMOMGMOMOMOMOMOMGOMMMMMMBBj  iirINXPNGEGGMGOOBBi iNBGOGOGOGOMOrOMMGOGMOMMOPuriiivuLvvuJYLYLLiEBBMMOMOOOMMMOOGOGOOEkkNOGOGMBL LFNNZNGEZXMPi
MGOOOGOGOOMOOGOOMOMOMOMOMOMMMOMOMOMOMBBJ  iiLFkUPEGGOOMOMBM  iGMGGGGOGOGOMJvBOOGOOMMBNJi    vvYIkUUujJuvvMMMMGMMBMMOOGMGOOOGGSPNOGOGOOBriUVXNNENGGBVik
GOGMOOGMGMOMOOOMGMOMOOGMOMOMMMOOOMMMOBBBY  irUFISOZGOOGMMBE  iNMEGGOGGZGOMGiFBGGGMOBOJi   rPPFuUuUVIuYYruBMMOOOZEGGGOOGZOMGOPXNOGOOOOMBvioSNXNNGGBLiNB
OGOOOOOGMGMOMOMGMOOOMOMOMGMOMOMOGGMMMOMMBL iivSoVEGGOGOGMBX iiPZGGGZOGGZGGMViGMGMMMOFiiioMBZFuFVVVIUojjvGBBGZOONONGGMOOGOGOGEEOGGZGNGMMivuSPZNOMMiiOBM
OOOMGOGOOMOMOOOMGOMMOMOMOMOMOMOMOZGBMMMBBBL iivSUNGOOMOOMBF  iXGNMGGGOGOEGGBLrMBOMMqJJNBBZXPSPXqqSJjuuIEBBOqZMOBGOOMGOGOGOGGZGOOOOEZZBV iIqEEMBS iBBBJ
MGOOOGMOOOMOMOMGMOMOMOMMOOMOMOMOMMGEBMMMBMBY irvuXZqOGZGBBP iiNGGGOZGGOEGNGOBJrEMGGNMBBGNPNPqPqSPFkIkPOMBMNqMOMMGOMOOOOGOGOGOGGGOGGZOBv vVEEBMi UBBGi 
GOGMOOGMOMGMOMOMOMOMOMOMOOOMOMOMMMMZqMMMOMBBv rjvkSUIkkMMBNiiiUOEEZGEGNZNGGMMBXkZGEOGOZGNENNPNXkVPSEOMMMMOXOOOOOMMGOGMOOGOGGZGZGGGZOOBriSGGBU  MMBMq v
OGOOOOOGMOOGOOMOMOMOMOMOMOMOMMMOMMMMONOMMMBBBY rFIVvYuEMBBOiiiJGGNGEGENNGOMGOOMOOGOGGEZZGNZNEqPSXNGOMOMMMNGOMOMGMOOOMGOGOGOGGZOZGZGEMMYoOBBi JBBBBGOBB
OOOMGMGOOOGMOMOMOMOMOMOMOMOMMMMMMMMMMMNGMBMBBBJ iNXUYXGBMBBLiirGOGGGEGZOOMGOGMGOGOGGNZEGEGNENqPEEOMMOZOMZNGMOOOOOMOOOOGOOOGGGGEGZGZGMMFMBu iMBBBBV FBG
MGOOOGOOMOMOOGMOMOMOMOMOMOMOMOMMMMMOMMMNGMMMMBBu iqkFPOMMOBNiirUMOGNGGMGOGGGOGGGMGZZGEGEZZENNqGOMOMOENMOEGOOOGMOOGOGOGGGOGOGGZZGGGZEMMBO  kMBBBS   OBN
OGGMGOGOOOGOGOOMGMOMOMOMOMOMOOOMOMOMMMOBZZMBMBBBF iNkZGMMMMBviirPMMMOMOMGOGOGOGOGOZGZGZZEGEZGOOMOMGZZBMMGOOMGOOOGOGGZOGGGGGOEZGOGGEOMMr iBBBBZi   iBBq
OGOGOGOGMGOOOGOGMOOOMOMOMOMOMOMOMMMOMOMMMGNOBMBBBU iNGMOMNOBNiiiLZMMOOMGOOOGOGOGOGGZOEZEGGGGMOMMBMkkMMOOMOMOOGOOMOMOOGOGOGMGqZOGONGOBVrMBBBGi   iiVBMk
GGOOGOGOGOOMGOOMOOOMOMOMOMOMOMOMOMOMOMOMOBONGBMMBBS iOMBOqSOBLirrFOBOMOMGMGOGOGOGOGGZGZGGOOMOMMBOrrMOMGOOMOOGMOOOOGOGOGGZZEZqOGGGOOBFOBBMBi   iiiiMBOk
OZOGOGOGOGOOOGOOOOMOMOMOMOMOMOMOMOMOMMMOMMBMNZBMBMBq iBBBVkqBGrirvNGMOOGOGOGOGOGOGOGOGOGOGMMBBMXiiZZBMMGOOOOMGMGOGOZOZGZGEZNOGOOMMEvUBBMi   ivvirLBBOV
GGGOOMOOGOOOGOGOOMOOOMOMOMOMGMOMOMOMOMOMMMOMMGZMMMBBP rBBkNMBBkrrvjEGMOOGOGOGOGOGOOOOMOMOMBBOViiiPrBMMOOOMOOGOGOGOZOEGZOGGNGOMMMEouMBMi   ivvLrirPBBqu
OZOGMGOGOGOGOGOGMOMGOMOGMOMOMOMOMOMOMOOOMMMOMMOGMMBBBP oBNOMBBBUvvLFZGOOOGOGOGOGOGOOOGOOMMGSjrYuBiZBOOOGMGOOOGOGGZGZGGGGOZNMMZqSOMBj    iLoUYvvvvOBMqj
GGZOGOGOGOGOOMGOGMOOGOGOOMZMOMOOOOOMOMOMOMOMOMMMOMMBBBFiOBOMMBBBoYLoPGOOOOGOGOGOOOOOGOOMNSFXXBOMUNBMGGOMGOGMGOGOOOGGZGOOOZPNNOBBOr    ivjkSVJLvuUBBGVj
OGOZOGOGOGOGOOOGOGOOMOOGMMOGMGMOMOMOMOMOOGOOMOMMMMMOMBBVYBMOMMBBBFUUPNOGOGOGOGOGOOMOMOZSPEGGBNYGMBBOOGMOMOOGMOOOOOOGOZOEGNMBBBL     iiYuuLLvLvvrZBBNkU
OOOOGOGOGOGMGOGMGOGMOMGOOOOMOMOMOOGMOMGMOMOMOMOMMMOMMMMBFGMMMMMMBMXXPEGMGOGOGOGOOMOMGqkGZZZOGiqVBBOOGOGOOMOMOOGMGMGOGGOBBBBSi    iirvLJLvYLLvvrvBBOEqk
MGOGOGOGMGOGOOMOOOMGOOOOMOMOOOOOMGOOMOOOOOMOMOOOMMMOMOMMBNMMMMMMMMMkPZOGOGOGMGOGOOONNNZNENOOjMviBMOGMOMGMOOGOGGGGZOOBBBMFi    iiirvLLvvvLLuvvvvPBMOPBu
GOOOGOGGGOGOOMOOGOOOOOOMOMOMOOOMOMOMGMOMOOOOOMGGMMMMOMOMMMGMOBMMMMBMNZOMMMGOOBMMZGZGEOGOGOMEOZ BBOGMGMMMGOGOOOOMBBBBOFri    iiivLvrvvYvLvJLvJUIBBBGGBi
MGOGOGOZOGOGOGOGOOOGOGMOMOMOMOMOMOMOMGMOOOOOMOMZGMMOMOMOMMMMMOMMMMBMGSPqZGMOMOMGGGGGZEOMMOOGB NMBGOOMGOOMOMMMBBMMXjrirLi  iirvoVvrvrLvLLUVXSkoEBMOGBv 
OOGOOOGOGOZOGOOMGOGOOMOMGOGOOOOOGMOMGMGMOOOMOMOOqMMMOMOMOMMMMMMBMBBMNOZGNENOGkqOGOGOGGNVMMOBj jBMMOMMBBBBMGONXPFLLvuqqiiiiiLjoqVirvLvJukNqkPIVMBMBBP  
MOMOOGOOGGOGOGMGOGOGOOOGGGGGGGMOMOMOMOMOOOMGOOMOZXBMMMMOMMMMMMMMMOBONNGGGZGGMPEGOZOOMOBL ZBM   PBMMOZPqujuVVkXNPqNGZEviirrLVSFNLrrrLISqXqSVVINBBBNv i 
OOOOGOGOGOGOGOOOOGEOGMOMMMOMOMOOOOOOGMOOOMOMGMOOONZMOMOMMMOMMMOMMMMBNZGGGOGOONXMGOGOOOMGIMGirPiurrrLvuIPqGOGNGNZGOEEqvivrvIXZMVrrJUPNZNNkkFPOBBIi  iii
MGOGOOOGOGOGOGOGOGOOOGOOOOMOOOMOOOMGMOMGOOMOOOMOMMMOMOMOMOMMMMMMMOMMEqGGOGOGMPNOOGOGOGMMBBPiBBBMOOMMBBBOMGGZZEOOGNZqkvvrvvkqGurLPOBBBBMOBBBZXv   iiii 
MMOMOMGMOOGOGOGOGOGOGOOMOMOMGMOMOMOMOMOMOMGMOMOOGMMMOMOMOMMMOMOMOMMBONZGZGGMMOMBMMOMOMOMMMiOBMMMOMMOOOOGGOGOOMGONGEZuvrvjEOOFFMBBEuri   iii   iiiiiiii
MOMMMMOGMGOGOGOGOGOGOOOGOOMOOOMOMOMOMOMOOOMOOOMGOOMOMOMMMMMMMOMMMOMMBNZZOGGBOoXEBBBMBMMMBYIBBOOOOGOOOGOGOGOMMOOGMGMGLrLUMBBMGIvi     LBk    iiiiiiiii 
ZGOMMMOMOMOMGOGOGOGMGOGOOMOMOMMMOMOOOOGOOOGMOMOMGOGMMMMMMMOMMMMMOMMMMMPNNOOBi i  rXBMOBOqLBZLMGOGOGOGOZGZOGOGOGGGOMMoVNOXLi          ivBBq   iiiiiiiii
qkEZMMMOMOMOMGOGOGOGOGOGOGOOOGGEGGOOMOMOOGOOOGMOOGOGMOMOMOMMMOMOMMMOMMMNPNMuiPBVi i  vUijGN JMMGOGOGOGOOOOMOMOMBBBBMori         i i     SBBU  iiiiiiii
XVIVXOOMOMOMGOGOGOGOGOGOGMOOGMOMOOOMOMGMOMOMGMOMOOGOGOOBMMOMMMMMOMOMMMBMPEUuMBMBBBMjrjiSXBuEMMOMGOGOOMMMOMOMBBMBOUi      i iii   i       iBBBi  iiiiii
OkULuIEEOGMOOGOGMGOOOOMOMOOGMOMOMGMOOOMOOOMOMOMMMMMOOGGZOOMMMOMOMMMMMMMMBqPMBOMOMMBBBOBuBBBMMOMGMOOGMOBBBBBBMr  rii   iii   i     i        qBBo  iiiii
OONSIVkEZOOMOMOMGOOOGOOOOMOMGOGOOOGMOMGNSkqZZMONNOOMMMOMGMOMMMOOOMOMMMOMMBGOGOOMOOOMMBVkBMMMGMOMGZGBMBOEPGMBNuLILii      i   i     i        MBBo iiiii
JkMOOEGZOGMOOOMGOOMGOGMOOGMOOGMOOGOGMGZPXSPqENNIVFkXGZOMBBMMMMMOMMMMMMMMMMMGOGOOOGOMBGoBBMMOOOOGqOBOGENGBBBOkvi         i i   i             YBBB  iii 
 IBMOMOOGOOOOMOMGOGOOMOMOOOOOMOMGOOMOOENPNNGZqXNXPkXkNNNXqkGMMOBMMMMOMOMMMOMOMOMOOOMMPOBOMOOOMMMMMGOMBMNri                       i   i      vBBZ iiiii
iXBOMOOGGZGGOGOGGZOOMOOGMOMGMOOOOOMOOGGqEEOGGPNqNqNNZEZPXFSSNNMOBMMMBMOOMMMOMOMOMOMOOqBMMOMMBMMOOEkori                        i   i         iBBY iiii 
ZMOOGMGOZGZZZOZOGOZGGOOOOMGMOMGMGMGOOONNNOOONNNZNGEGEEqNPNPGGBMMMMGGMBMOOBMMOMOMMBMBGFMBMBBMGMOOGGqNkPNONFLLriiiiiii iiiii i i              iBBi iiiii
MOOOMOMOOEZNGZGOMOENGGMOMOOOMOMOMMMOOGENGOMNENZNZNGGENZNNNZNGGOGZXVoMMMGMMMMMOMMMMBBBBBBBBMGEkZOMOBOMOEPPXNXNNGqPUoviiiiiii i   i     i     iBB iiiiii
OOGOOMGOOOZOGOENNOOOGOGMOMOMOMOMOMOOGGEZGMGNEGEGEGGONZNEEGNqXZZOENFVNBGOMMMMMMOMMBBMBGJi irLrjGBGMMMMBEFJLiiiiiiiii      i i i i     i      iBE iiirrr
OGOOMOOOOGOOBZFuvkBBMMOGOGMGMOOOMOOOOZGGMOGZZZGGOGOEGZGNGZGXEEGGOOONPNMOOGMMMOMMBBj       rqGGqoqNZMGqMBBBBEYi  irrii iiiiiiiii   i   i     oBv irrvr 
GGGOGOGMOMBBGkoviJGBBBOOGGGOOOGOOMOOOGZOOOEGGGGGGOGOGGEENGGZXNNGZOOOGGGGGMOMMBBBBS         ZOYSMOIrviiFurBBv MjirivYriiiiiiiiiii ii         BB iivri  
OGOGOGOOMMMqYrLi iJXBBMMMGOOMGOOOOOGOZOGMGGEOGOOMGOGOGOZOGOZEXNNZZGGOZOGOOMOMMBBU     i i iPVJMMOEFjr iYirOJoNiiiiivLiiiiiiiiii   i        iBS iri  iL
GOOOGMMBBBUiiiriii iOBBBMMOOGOGMOMOOGOOMGGGGZOGOGGGOGOGOGGOONqPNNZNENZZGZOZMMMZYi      iiiivuEGGNPIoLiiruVPGui       i iiiii i i i i   i   OBiiri  ruN
OGOOMOGMBUiiiiiiii  LBBBBOMOOGOOMOMOMGMMOZOGOGOGGZOZOGGZOGMOZNNPNPZNZEZEGZGOBZjri     i i i irXGOGZXPkXuLii         i iiiiiiiii i     i   iMq r  iLFEj
OMMBMNvoPi iiiiiiriiiiXBMBMMOOOMOOGMGOGOGGGOGOGOZOOOGGZOGOGOGEqNqNqZNZNGEGEOOSLii i    i i     iJNqNPqIJvii  i iiiiiiiiiii i iii     i    BBi   ijFEU 
MMMMMjrriiiriiiirrLvi iJqMBMMOMOMGOOMGMOOGOGMGMGOGOGOGOGOGOOMGNqNPqqNNZNZNGMMoviiii              ivYuULiriiii   iiiiiiiii i i i   i i i  GBu  irukPv  
BGrvNqSr  iviiirviiri  iiYGBMMOMOOOOGMOOGOGOOOGOGOGOGGZOOOGOOMNNNNXNqNPNqEGMOIviii     i       i   iiviiiiiiiiiiiiiiiiiiiiii            UBO  irUSIi  v
BL  Ujii  ivJriirii i  ir LOBMMOMGOOMGMGOGOGOOOGOGOGOGOGOGMGOMOqGNNPqPNqNNOMOuriiii   i     i   iii iiiiiiiiiiiiiiiiiii i i   i i i    kBr  irUPL   UM
vi iPr ii  iJIiiiii  iiLviiPMBMMGOGMGMOOGOOOGOGOOOGOGOGOGOGOGMOONZXqPqXNPEOBZoii i           i   iiiiiiiiiiiiiiiiiiiiiii i iii   i   iBB  irLNPi  iEBB
rLIiov  iii ijvriiiiiiiivLvuMBMOOGOOOOMGOOMOOOOOOGOGOGOGMGOGMOMGGNEqqPNXqNMBELi i     i i i i     iiiiiiiiiiiiiiiiiiiii i iii i     vBN  roXGo   JMBBU
UFBJiLi  rrii iiiiiiiiiiiuuLNMOMOOGMOOOOGOOMGOGOOOGOGOGOOOGOOMMOMGNZNNPNqGMMVv       i   i   iii   iiiiiiiiiiiiiiiiiiiiiii i       GBi irNZOr  iIMOZv 
Siuv iLi iULi  iiiiiiiiiivjirSMGOGMOMGMOOOMOOGEGOGOGOGOGOGOOOOMNMMGNNqqNZEMEYi  i i     i     iirii iiiiiiiiiiiiiiiiiii i iii    rBZ  iJNONi  rNNXoi  
U  v  JBji iii iiiiiiiiiirr rMMOGGGMOMGOOOOMGGGOGOGOOMOOGOOOGMMqGBOZEGNENOOkiiii         i      rjriiiiiiiiiiiiiiiiiiiiiii i    MBr ivuGMS   oPXVvi  N
X  vF iGOi  iiiiiiiiiiii iiuBBMOOGOMMOOGMOMOOGMGOGOGOOOGOGOOMOOVBMBOEEZNNPPuiiiii     i   i     iLqUriiiiiiiiiiiiiiii iii     IMO  rvYNOv  ioSVjri  OB
Uu vBqi ii iiiiiii iiii  iBBMMOONEGBOMGOOOOMOOGOGOZGGOOOGOOMOBUoBBMBGZEZqIvLii i         i     irvjNNuiiiiiiiiiiii i i      vBBi irrrqX   rFJvri   BBF
rMSvBBri  iiiiiiiiiiii  iBBBMOZPNPLZBOOOMGMGOOOGOGGGOGOGOGMGMMkuBMMMBOGGNuLvi                  vuvriLSEYiiiiiiiii i       LBBu  rrivNY  ivuuLii  iBBO 
rNMGuiiriiiiiiiiiiiii  vMBMMGOEOBv OBMOMGOOOGOGOGOOOGOGOGOGOGMMLEBMMMBGEZkuoLi         iiiiiiiiiiiiiiivUYviiiiiiiii     vBBE  irrrUOi  iruLJri  iBMO  
UoZoi iiiiiiiiiiiiii  LBBOGOOGMBU SBMOMOMGOGOGOGOGOOOGOOMGOOOGBELBBMMMBNZGNFkui    iiiiiiiiiiiiiiiiii iiirriiiiii    ijMBBr iivrvkU  iiiJvrii  rBBO  i
ONLriiiiiiiiiiiiiii  vBBMMOOOMBq LBBOMOMOMOOOOGOGOOMGOGOOMOOOMOBuNBMMMMMGGGOOMMSvuOBOi iiiii iii iiiii i iiiiiiiii rFBBBBr XvLLuUi  iiirriii  jBBZ  rS
juviiiiiiiiiiiiiiii rBBMOOMGMMB iBBMMOOOOOMGOGMGOOOOOOOOOGMGOGMMGVBMMMMMBGGGMMBBBBMMMvi i iiiii iiiiiiiiii  iiiiiijZBBBBMiuNuLoi  iiiiiiiii  IBBG  LSZ
rrvrrrriiiiiiiiiii iMBMMOMOMMBi BBBMOMGMOOOOGOGOGOOOOOOOOOOOGMOMMPNBMBMBMMZGGGGMOPuqMNriiiiiiiiiiiiiiiiiiiii iiiirXMMBBBBIjSrv   iiiiiiiii  NBBE  ukXG
rivrrrrriiiiiiiii  OBBMOMOMMBN JBNPMMOMOMOOGMOOGOGOGMOOGOGMGOGMOMOIOBMMMMMMZOGGNEuiiEBorriiii   iiiiiiiii i   iiivqMMMBMBroi   iiiiiiiiii iNBBX  VPSEE
uLvvrrrrriiiiiiii iBBMOMMMMBBi BBXuBMOOMOOGOGMGOGOGOOMOOOMOOGOOOOBNFMBMMMMMMZGOMOOJvruriiiiii      i iiiiiiiiiiiruEBMBMBMNqv iiiiiiiiiii iMBBP  XNkGPN
uLJvvvrrrrriiiii  BBBOMOMOMMB VBGGNOBOOOOGMGOGOOMGOGOGOOMOMOOOMOOOBINBBMMMBMMZGGMBBMMNPoFuULvriivvvvLrvYVjvrriirvoOOMMBMMMOVviiiiiiiiii iBBBF iNNXPZOM
uJJjLLvvrrrriiii rBBMMOMOMMBv BMZOZjMBOMOMOOOOGMOOGMGOOOGMGMGOOOOOOMVOBMMMMBMMZGZGGBMBBBBBOBMGqkPSviiiiiiiiiiiirjZGMMMMBGOGIriiiiiiiii rBBBV rGNkNPOOB
PUuYjYYvvvvrviii EBMMOMOMMBMiUBOOGMLUMMOMOOOOOMGOGOOMGMOOOMOOOMGOGOMZSMMMMMOMMMGOGZNqNENEqFvrrii  i i i i iiiivLqOMOMMMMNOBFiiiiiiiii LMBBu vMZPPNMMBO
OGFoJJJJvLvrrriiiBBMOMOMOMMMXMOZZOOOLGMMOOGOOMOOOOOOOOOOOMOOGOGMOGOMMNNBMMMMOMOGGOGZoIkGPSVJii   iiiiiiiiiiiiivVZMOMOBMMqBBriiiiiiii uBBMu YMGNZZOBBGk
MOONIjJLYvYvrii uBBMMOMOMMMGOMMNZGOOOXGMMOOOOOOGOGMGMOMGMOMGOOOOOGOOMOqGBMMMMOMOZNOGOEZZZIqENuriiiiiiiiiiiiirrLVOOOOMMBOEBBiiiiiiiiikBBBv oMEZGMBGOEPk
OOMMqkuJLJvvrriiOBMMOMMMMBMGOMOOGGGOOGqOMMOOOOGMGOOMOOOOOMOOOOGOOMOMOMGqMBMMOMOBENPNqNNENqPkIJvriiiiiiiiiiiiirvVZOGMMBBONBEirLvvriiZBBBL kMNEGOBOOXXGM
MOMOMNkuYLLvvriiBBMOMOMMOOBPOOOGOEGOOOOGOGMMMGOOOGOOMGOOMOMOOOOGOOMOMOMEqMBMMOMMONNkVuFkILvrriiiiiiiiiiiiiiiiivIGOMBBMBEOBSivvYLrrZMBBL NMGZGOMZNPEGOZ
OMGMGOPkujLLvviUBMGMMMMMGBONGEZOGGEOMMOMZqqqOMOMOMOMOMGOOMOOOOGMOMOMOMOBqXBBMMMMOGNNVUuIjjriii iiiiiiiiiiiiiiivNMBBOvVBGOBLirvrrrOMBBLiEMGNMOMNXPOOOOG
OGMOGGGPIujLLrikBGOMMMMMOMOZOqGGOGGGOGOOOGGSSNBBBOMOMOMOMGMOMGOOMOMMMOMMBjIMMOMMMMONPjjuuuvriiiiiiiiiiiiiii iiUGBONuLEBNBBrivriiGBMMYrMOMOMOONEGOOOGOG
OOGOOGZGkVuJvriMBBOMOMMMMBEOGGGZEGGGNOGONMOOENUFMMBBOMOOOMOOOOOOOMMMOMMMMBiYOBMMMMMMZkYJJjLriiiiiiiii  i    ivNBOGNGGBMZBZirrirMBMGvrMMOOMOGXZGMGOGOZZ
MGMOONOGGkuLvriOBOMOMOOOMOqOOGONNGOEOGOEGOOGMMvJOUVMBBBOOGMOOOMOMOMOMOMOBBOioMBOMOMMBOESVJYviii i          iVMBMMOOGOMMEBSirrvMMMGESMMMMMGENMOMGOGGGOZ
OOOOZGGOZEIuLriMBMOMMMMMMMqOOOGGZOGGGMMZGMGMMViMGXLvLqMBMOGMOMOMMMOMMMMMMMBOIMMOOMMBMBBBMOXILrii        iYNBBBMMGMGOGBGGBVirLMMMGGGMOBMMGNNMGOGOGGGGGG
OGOGOOOGGNNVjrrGBOMOMOMGMOEOOGOZGGOEMOMZOZOOMLPONNZPYiuOOOMOMOMOMOMOMOMOMOMMBMMMMOMMMMBBBBBBBMMNXVPXEMBBBBBBBMMOOOOGOMOGBLiUMMMGGZOOEMMEEGOGOGOGOGGZOG
GMGOGOOOOGZONPPMMMOMMMZMMOVOEGZOOMENOMOGGOGMGMMGPqPEkEONPOMMOMOMOMOMOMOMOMMMOMMMOMOMOMMMMBBBBBBBBBMBBBBBBBBMOMOMOOOOOBGMBvuBMOZGGOOBMESGGOGOGOGOGOGGZZ
GPOOMOMOMGOMMMMGMGOOMOMOBMMOOGZEOOZZOGOGOGOOENMGGqNFXMGNMOMMMOMMMOMOMMMMMOMOMMMMMOMOMMBMBMBOOMBMBBBBBMBMMMMOMOMqOGOGOBOGMNMOOZOZMMBOGXGOOGOZGGOOOGGZGN
OOGOOMGMGOOMOMMMOMOMOMOMMNVBOOGGEOZOOOZOGOGOqMGZEGkPOGNMMMMMOMMMOMOMOMMMOMOMMMOMOMOMMMMBMMMMMBMMOMMMMMMMOMOMOMOOGOZOGNqOOMGGZOOMMOGNqOOMGGGGGOZGqGEZEP
MZOOMOMGGGOOMOOOOOMOMOMOBr BMGGGMNZOMOOGOZGEGOOGOGPUBOMOMOMMMOMOMOMOMOMMMOMMOOMMMMMOMMMMMMMMBMMMMMMMMMMOMOMOMOMGZZOGOEOOOGOGOOMMMGNEOOOGOGOGGEONNEGEZu
ZZGMMGqXFqOMOOGOOOOMOMOMMEVBGGGOGGGOOOGMOOEEOOGOOBvLMMOMOMMBMBMMOMMMOMOBMMOMOMOMOMOMMMOMMMOMMBMBMMMMMBMMMMOMGOGGEGNZGOGOGOGOOMOMNNEOGGZOEGEGEZEGZZPPkV
MGZPPVFIUSOMMGOGOGOOMOMOMMBMMOGEMOOGOGOOMOOqGZOGOqLGBMMOMGGZGGBMMOMMMOMNOMMMMOMOMMMMMOMMMMMMMOMMMOMMMMBMMOMOOGONENENGPGGGZGOMOMSFEGEGNNqqNNNZNNqENNkqF
GqFFVFUVuVNOOOOMOGGMOMOMOMMBMMGOGOOMGGGOOMZZGZNGEZMBMMOMMMGGqvvBBBMMOMMNPMOMMMMMOMOMMMOMOMOMOMMMOMMMOMMMOMGMGOGOZZNZPPEGNGOMMBEoXEqEXPkNPNNENZNGEGPNPS
ZVSVVUFVFINGMOMGOGOOOMMOMOMMBOMGGNMOMGGGGOEEOGGNEMBOMMMOMMMMBMkrMMOOMMMMMMMOMMMOMOMMMMMOMOMOMOMMMMMOMMMMMMMOMGGEEqENNNGNOMMMBMOVqqNSPSXXqXNNEqZEOENNEk
NFIXSPPZZGEOOMGOOMGOMMOMOMOMOMOOGGGOOMGOZGEGZOEOMMMMOMGMMMOMMBBi BMMOMOMOMOMMMOMOMMBMMMMOMOMOMOMMMMMMMMMOMOMGOGGqNPNPNNEOBMMMBEkXqkXkPqNXNqENENENZNGNX
XFNEGZMOMOOGGGMGMOMGOGMOMOMMMOMOOGGqGOOGOGZZOGOMMMMGMOMOMMMMMMBBiqBMMMMOMOMMMOOOMMMMMMMMMOMOMOMOMOMMMMMMMOMOOZGENXNXNNGOMMMMGGMkVVVFXkqqqqNqEqENNNEENF
NGOMGOGOGGGOGMOMOMOOGOOMOMMMMMOMMOGGZGZOOONGZOOMMMGGMMMMOMOMOMMBSuBMMMMMOMMMGOOMMMOMOMBBMMOMOMOMOMOMMMMMMMOMGGNEPqPqqZMBOMMMMMONoIokSqqNNZNEqNqENZNNPS
MGOGOGOOOGONNZMOOOOOGGOMMMMMMMMOMMOOMGZZGGOGMOBMMOOOMGMMMOMMMOMMBuBMBMMOMMBZGGMMMGOGOGXuMMMMMMMOMOMOMOMMMOMOOEZZNqNPEMBOMOBMMOMZXIkSXNGNNEZqqXNEZNEqNX
GGGOOMZZqNFVoXGMOOOMOGGMMMOMMMOMOMMMBBMONqZGMMMMMOOMOOOMOMOMOMOBBivBMMOMBMqEGMMMOOGOGOokMOGMMBMMOMOMOOOMMMMMGGZGqPkqGBMMMMMMMOMMEPkNNNNENZPNPqNEqNNENN
OEOZZPXIIUIuuIZOMOMOMGOOMOMOMMMMMMMBGiOBMEGOMOMMMNOMMOMOMOMOMMMMB  MBMMMOuXOMOOOMMMOONOMOGGNNNMMBMMOMOMMMMMMMGGNNkqZBMMMMMMMMMBGONNEGNGZENkqNNNNNqqNZq
OGZZSoouJouIVFkOMMGMGMOMMMOMOMMMOMMBZ rBMMOMOMOMOXZMMMOMOMMMMMOMBi BMMMGVNOBBBMBOMMMOMOOGOGGXjEGGMBBMMOMOMOMMMEEXkPMMMMMMMMMOMMMGGZGGOZZNZNZNENENNqZZN
MGONkjYYuoSkNNGGMOOOMMOOMMMOMOMMMOMMB  BBOMOMOMOMZOOMOMOMOMOMOMMBUvBBMOPGOMBGvBBMOMOMOMMMGOGNEMqqXNZBBBMMOMOMOONESZMMOMMMMMMMMMOOGGEGEGEGEZENNEqZNGNEk
GOGZPIvYFEGMOMGOGOOMOMOMMMMMOMOMOMMMBN PBMOMOMMMMONMMMOMMMMMOMOBZPBBMONGOMBBv MBMMMMMMOOGMOMOMGZNNkviGBBBBMMMMOGqXGBMMGMOMOMMMMGGGZZNGEGZGZZqNPNEZNNNX
OZMGONkVNOMGOGOGOGOOBMBOMOMMMMMMMMMMBB iBMMMMOMMMMNEMMMMMMMOMOBOIOBMOqGOMMMMOGiGBMMOMMMGOGGGMOZEZNVrrkGJuMBBBMBMZNMMMMMOOMMMMOBOOGGZGEGZGZZNNNENGNEPqV
GOGOOOZNFNGOGGZOOOOMGNEMMMMMOMMMOMOMMBY BBOMMMOMOMOOOMMMMMOMMBO uBMESZGMMMGOBu EBMOMOMOMMMOMOOGOOEJIGMPuivuNBBBBOBMMMMOMOMOMOMMBGOEGEGEGEZNENGGGEZPqqF
GGZSMGOkjjGGOGOMBOGFuvuZBOMOMOMOMMMOBBM jBBMMOMOMOMMMMMOMOMOMMMEBMqUEOBMOSNBBi BBOMOMOMOMOOGMGGEGZMBMNqFPJ iMEOOMGBMBMMMBMBMMMMOZGGZGZGZZNZNGEZNENNNNV
EGZZZOGZuLVMGOOZSoYLvvrPBMOOOMOMOMMMMBMi BBMMMMMOMOMOMMMOMOMOMMBMGSNOBMMZkNBB vBMMOMOMOOOMOMOOOGkOGOMOXPF iMkVVFi rBMMOMBBBBBBBGIOZGZZNGNZEGZGEEEEqNqX
OqGEEEOOSJVZMOEuvvvvvvvNBMMMMOMMMOMOMMBk kBMOOMOMMMOMMMOMOMMMOMMMZOOMMMNENqBO ZBMMMOMOMOMOMMMOOOMGuivMBOi NGqPkui rMGFIIXuiqBMMMENZEENNNEZGZZEZEZPNPNS
ZEEZEZGMqVVGOMZFLrvLJIFMMMMMOBMMMMOMOOMB  BMqOGOOMMMMMOOOMOMOMOMGOMBMOENGMkBF MBMMOMOMOOOMOOOMMMOMZViiYMYPMZPZNS  OBGPSSv  NMOZMEEqNXZNGNZNZNZEGEEPZqN
EPEZZNGOZVPOMOOEIvuFOOOMMOMOMOMMMOMOMMBMv ZMMOMMMOMMMOMOMOMMMOMOMOMOMGGOMOOBV BMMOMOOOOOMOMOOOMOMOMMMIi XBMGMOBOUSBGGNEPL iBBBMMMNqqNEGGGNGNGZGNZNZNEP
qqEGNGZMENPMOMOMENGMOONMOMMOOMOMMMOMOMMBM  BMMOMOMMMMMMMOMOMOMOMOMMMOOOMGMGMYiMBMMGMGMOMOOOOGMOMOMOMMBBMBMOMOMMBMBMMOMMMMMBBZEZMMEXNEGZZqGNGZZZOZGEZqP
NPEqZGMOVuEMMOOOMMMOZEEGMOMGOMMMMOMOOMMBBi qBMMMMOMMMOMMMOMOMOMMMMBMBOOOOGMUriBMMOMOOOMOMOMOMOMOOOMOMOMMMOOOMOOOBOMOOOOGMMGuLirOBNNNZEGNqGGZGZGEGNZqNX
kkPNNMOYiiXBOMGMMMOOGENMMMOMOMOOOMOMOMMBMG iBBMMOMOMOMOMMMOOOMMMMMOSMBOOGMMqiiMBOOOOOOGMOMOMOOOOGMOOOOOMGOOOGOGOGOGOGGGGEGEPVYjBBMEGZEEOGZENPZEEqNXqXX
SVqNGMNi  XBMOMGMOOGOqGOMMMGOOMOMMMOMOMOBBi GBMMMOMMMOMOMOMOMMMOOMBvNBMOMOBNriBMMOMOOGMOMOMOMGOOOOOOMOOGMOOGOGOGOGOGOGOGOZNZGZMNBOZNZZZEGEENNNENNqZNEk
SFqGGMui iMBOOOMGOGOZZGMOMMOEOOMMMOMZOMMBBS  BBBMMMMMMMMOMOMOBMMOBBIjBOOOMMGYiSBOMOMMMOMOMGMOOGMGMOMOOGOGOGMGOGOOOGGGOGOGqZO rkjMMEGEGEOZGNZNEGZZMOMMM
VSqNGNuirEBMMOOOOOOGGNOOMOOGMGOMMMMOZEMOBBB  XBMMOMOMOMMMOMMMuNBBMBGJOMOOOBGUirMMOOOMOOOMOMGOOOGMOOOOGOGMGOGOGOGMGOGOOMOGGBJiESoBMGGGZOGZNZGMMBMBBBOMO
VSqZGZFSGBMMOMOMGMOMGEGOGMOMOGOMOMMMGOOMMBBo  BBMMOMMMOMOMOBBkiOBBMBFNMMOMMOFL MBMOMGMOMOOOOOMOOOMOOGOGOOOGOGOGOGOGOGOGGGMZi MXkMBGOZGEZGOMBBBOOENVSoj
qkOOMOMMBMMMBMBMBMBMMGMOMGMOMGMOMOMMMGMMMMBB  FBBOMMMMMMMMMOBBviBBMBGFMOOOMGXNijBMMOMOOGMOMOOOOGOOOGOGOOMOOOOGGGGGOGMGGGMGN iGUJBMOGOGOEBBBMZXXUuLuoqN
NZGMMMBBMBMBOMMMBBBGPEMMMMOMOMGMMMOMOGOMOMMBu  BBBMMOMOMMMMMMBBijBMBMPGMOMOMXGJiBBMMMMOMOOOMGMGOGOOOGMGOOOOMGOGOGOGMOGOMGGXivULjMBGOZOOBBGIVFkXNPqqqqq
r rvvjJvUvrVqSPvvvv  vIMOOMOMOOOMOMMMZOGOOBMB  iBMMOMOMGGOMOMMBNiIMOBZNOMOMMZEOivMMOMOOGMOOGOOOGOGOGOGOGMGOGOGGGOGOZGGEUuuv vvrvMMOGGGBMv iVNNZNNPNNGG
*/

long long a[100010];
long long n;

int main(){
	cin>>n;
	long long sum=0;
	long long ans1=0,ans2=0;
	long long c=-1;
	for (long long i=1;i<=n;i++) {
		cin>>a[i];
		sum+=a[i];
		if (sum*c<=0) {
			ans1+=abs(sum)+1;
			sum=c;
		}
		c*=-1;
	}
//	for (long long i=1;i<=n;i++) cout<<sum[i];
	sum=0;
	c=1;
	for (long long i=1;i<=n;i++) {
		sum+=a[i];
		if (sum*c<=0) {
			ans2+=abs(sum)+1;
			sum=c;
		}
		c*=-1;
	}
	cout<<min(ans1,ans2)<<endl;
//	cout<<ans1;
	return 0;
}

Measured memory_bytes: 1024