تتدرب في مجموعة بحثية في المعلوماتية الحيوية تدرس الحمض النووي DNA. يتكون الشريط المفرد من DNA من جينات كثيرة تنتمي إلى فئات مختلفة تُسمى أنواع الجينات. تُحدَّد حدود أنواع الجينات بتسلسلات معينة من النوكليوتيدات تُعرف بعلامات الجينات. لكل نوع جين $i$ علامة بداية فريدة $s_i$ وعلامة نهاية فريدة $e_i$. بعد الكثير من الأعمال الشاقة (تنمية البكتيريا، واستخلاص الخلايا، وهندسة البروتينات، وما إلى ذلك)، تستطيع مجموعتك تحويل DNA إلى شكل لا يتكون إلا من علامات الجينات، مع إزالة كل المادة الوراثية الواقعة بين العلامات.
طرحت مجموعتك الفرضية المثيرة للاهتمام بأن تفسير الجينات يعتمد على ما إذا كانت علامات بعض أنواع الجينات تكوّن بُنى متداخلة بصورة صحيحة. لتحديد ما إذا كانت علامات نوع الجين $i$ تكوّن تداخلًا صحيحًا في تسلسل علامات معطى $w$، يجب النظر إلى التسلسل الجزئي من $w$ الذي يحتوي على علامات النوع $i$ فقط ($s_i$ و$e_i$)، دون إسقاط أي منها. تُعد البُنى الآتية، وهذه وحدها، متداخلة بصورة صحيحة:
- $s_i e_i$
- $s_i N e_i$، حيث $N$ بنية متداخلة بصورة صحيحة
- $AB$، حيث $A$ و$B$ بنيتان متداخلتان بصورة صحيحة
نظرًا إلى خلفيتك الحاسوبية، كُلّفت بدراسة هذه الخاصية، لكن هناك تعقيدًا إضافيًا. تدرس مجموعتك نوعًا خاصًا من DNA يُسمى DNA الدائري، وهو DNA يشكل حلقة مغلقة. لدراسة التداخل في DNA الدائري، يجب قطع الحلقة في موضع ما، مما ينتج تسلسل علامات محددًا بشكل وحيد (اتجاه القراءة ثابت تحدده الخصائص الجزيئية). لذلك أصبح كون نوع الجين $i$ يشكل تداخلًا صحيحًا يعتمد أيضًا على موضع قطع DNA الدائري. مهمتك إيجاد موضع القطع الذي يزيد عدد أنواع الجينات التي تشكل بنية متداخلة بصورة صحيحة إلى أقصى حد. يوضح الشكل D.1 مثالًا يقابل مثال الإدخال 1. يجعل القطع المشار إليه علامات نوع الجين 1 متداخلة بصورة صحيحة.
الشكل D.1: توضيح لمثال الإدخال 1 مع موضع القطع الأمثل له.
الإدخال
يحتوي السطر الأول من الإدخال على عدد صحيح $n$ ($1 \le n \le 10^6$)، وهو طول DNA. يحتوي السطر التالي على تسلسل DNA، أي $n$ علامة. كل علامة هي محرف $c$ يتبعه عدد صحيح $i$، حيث يحدد $c \in \{s,e\}$ ما إذا كانت علامة بداية أو نهاية، ويمثل $i$ ($1 \le i \le 10^6$) نوع الجين للعلامة. حُصل على تسلسل DNA المعطى بقطع DNA الدائري في موضع اعتباطي.
الإخراج
أخرج سطرًا واحدًا يحتوي على عددين صحيحين $p$ و$m$، حيث $p$ موضع القطع الذي يزيد عدد أنواع الجينات المختلفة ذات التداخل الصحيح إلى أقصى حد، و$m$ هو هذا العدد الأقصى. يُقطع DNA مباشرة قبل العلامة رقم $p$ في الإدخال (مثلًا، للقطع في الشكل D.1 لدينا $p = 3$). إذا أعطى أكثر من موضع قطع القيمة القصوى نفسها لـ$m$، فأخرج أصغر $p$ يحققها.
أمثلة
الإدخال 1
9 e1 e1 s1 e2 s1 s2 e42 e1 s1
الإخراج 1
3 1
الإدخال 2
8 s1 s1 e3 e1 s3 e1 e3 s3
الإخراج 2
8 2