Biển quảng cáo

Ông Nguyên là một chủ nhà hàng có tiếng ở QN, nhà hàng của ông có một dãy hàng rào vô cùng đặc biệt. Hàng rào của nhà hàng là một dãy gồm $m$ thanh gỗ liên tiếp, với mỗi thanh gỗ có chiều cao nằm trong đoạn $[1,m]$ và đôi một khác nhau. Nói cách khác, chiều cao các thanh gỗ là dãy $a_1,a_2,\dots ,a_m$ là một hoán vị của dãy số $\{1,2,\dots ,m\}$.

Dạo gần đây, nhà hàng vắng khách nên ông Nguyên quyết định mua một biển quảng cáo đặc biệt đặt trước hàng rào của nhà hàng để thu hút sự chú ý, mong phần nào cứu vớt tình hình buôn bán ế ẩm của nhà hàng mình. Biển quảng cáo ông mua về có độ dài $n$ ($n\le m$), kích thước tương ứng với $n$ thanh gỗ trên hàng rào. Cửa hàng biển quảng cáo cũng đưa cho ông một dãy số $s_1,s_2,\dots ,s_n$ là hoán vị của dãy số $\{1,2,\dots ,n\}$.

Gọi chỉ số các thanh gỗ trên hàng rào được gắn biển quảng cáo lên là $[u,u+1,\dots ,v]$ (với $v-u+1=n$). Cửa hàng hướng dẫn: để có thể gắn biển quảng cáo lên hàng rào một cách chắc chắn và đẹp mắt thì đoạn các thanh gỗ liên tiếp được gắn biển quảng cáo phải thỏa mãn (thứ tự chiều cao xét trong $n$ thanh gỗ $a_u,a_{u+1},\dots ,a_v$):

• $a_u$ là chiều cao nhỏ thứ $s_1$;
• $a_{u+1}$ là chiều cao nhỏ thứ $s_2$;
• ...
• $a_v$ là chiều cao nhỏ thứ $s_n$.

Yêu cầu: Ông Nguyên muốn biết có bao nhiêu cách đặt mà biển quảng cáo của ông sẽ chắc chắn và đẹp mắt.

Dữ liệu vào

• Dòng đầu là $2$ số nguyên $n$ và $m$ ($1\le n\le m\le 2\times {10}^5$).
• Dòng hai chứa $n$ số nguyên $s_1,s_2,\dots ,s_n$ ($1\le s_i\le n$), là một hoán vị của $\{1,2,\dots ,n\}$.
• Dòng ba chứa $m$ số nguyên $a_1,a_2,\dots ,a_m$ ($1\le a_i\le m$), là một hoán vị của $\{1,2,\dots ,m\}$.

Dữ liệu ra

• Dòng đầu chứa số $k$ là số lượng cách.
• Dòng hai chứa $k$ số nguyên là các chỉ số $u$ (chỉ số đầu của khoảng chỉ số $[u,u+1,\dots ,v]$ thỏa mãn đề bài) được sắp xếp theo thứ tự tăng dần. Nếu $k=0$ thì dòng này để trống.

Ràng buộc

• $1\le n\le m\le 2\times {10}^5$.
• $30\%$ số điểm thỏa mãn điều kiện $m\le 1000$.
• $30\%$ số điểm thỏa mãn điều kiện $s_1<s_2<s_3<\dots <s_n$ (với $n<m$).
• $40\%$ số điểm còn lại không có ràng buộc gì thêm.

Ví dụ