F. Цаасан дээрх ажил

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Алекс Валентинагийн (түүний хөлд орж буй охин) хажууд код бичиж байсан ба тэр кодон дахь дугуй хаалтуудын талаар маш их асуулт асууж эхлэсэн. Тэр түүнд бага зэрэг тайлбарлаж өгсөн ба Алекс кодоо цагтаа дуусгахын тулд түүнийг ойлгосоны дараа түүнд ажил өгсөн.

Энэ бодлогоны зорилгын хувьд бид зөвхөн '$($' ба '$)$' тэмдэгтүүд буюу нээх, хаах дугуй хаалтуудаас бүтсэн тэмдэгт мөрүүдийг авч үзнэ.

Хаалтуудын дараалал нь дараах нөхцөл биелэж байвал зөв:

  1. хоосон
  2. хаалтуудын зөв дараалал буюу нээх хаах хаалтын хос нэгдсэн
  3. хоёр зөв хаалтуудын дарааллын хэлхээ

Жишээлбэл "$()()$" болон "$((()))(())$" дарааллууд нь зөв бол "$)(()$", "$((((($" болон "$())$" дарааллууд нь буруу.

Алекс цаасны хэлтэрхий авч $s$ хаалтнаас бүрдэх тэмдэгт мөр бичээд Валентинаг $s$-н ялгаатай хоосон биш хаалтуудын зөв дараалал бүхий дэд тэмдэгт мөрүүдийг тоол гэж хэлсэн. Өөрөөр хэлбэл түүний ажил бол $s$ тэмдэгт мөрд дэд тэмдэгт мөр (дэд дараалалтай битгий холиорой) хэлбэрээр тохиолдох хаалтуудын хоосон биш зөв дарааллуудыг тоолох юм.

Валентинаг ажлаа дуусгахад Алекс хариултыг нь өөрөө мэдэхгүй гэдгээ санав. Түүнийг Валентинагийн өмнө үл хүндэтгэсэн байдалтай байхгүй байхад туслана уу мөн бодлогыг шийд.

Оролт

Оролтын эхний мөрөнд бүхэл тоон утга $n$ ($1 ≤ n ≤ 500 000$) байх ба $s$ тэмдэгт мөрийн урт.

Хоёр дахь мөрөнд $n$ урттай $s$ тэмдэгт мөр байх ба зөвхөн '$($' болон '$)$' тэмдэгтүүдээс тогтоно.

Гаралт

$s$ тэмдэгт мөрд дэд тэмдэгт мөр хэлбэрээр тохиолдох хаалтуудын хоосон биш зөв дарааллуудын тоог хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
10
()()()()()
Гаралт
5
Оролт
7
)(())()
Гаралт
3

Тэмдэглэл

Эхний жишээн дээр бидний тоолох ёстой $5$ ялгаатай дэд тэмдэгт мөр байна: "$()$", "$()()$", "$()()()$", "$()()()()$" ба "$()()()()()$".

Хоёр дахь жишээн дээр бидний тоолох ёстой $3$ ялгаатай дэд тэмдэгт мөр байна: "$()$", "$(())$" ба "$(())()$".

Сэтгэгдлүүдийг ачааллаж байна...