Bobo has ntuples(a1,b1,c1),(a2,b2,c2),…,(an,bn,cn) .
He would like to find the lexicographically smallest permutation p1,p2,…,pnof1,2,…,n such that fori∈{2,3,…,n} it holds that
ZZT 创造了一个队列 Q。这个队列包含了 N 个元素,队列中的第 i 个元素用 Qi 表示。Q1 表示队头元素,QN 表示队尾元素。队列中的元素是 N 的一个全排列。
ZZT 需要在这个队列上执行 P 次操作,操作分两种:
FIRST X: 将元素 X 移到队头。
LAST X: 将元素 X 移到队尾。
在 P 次操作之后,ZZT 想知道队列中的元素的排列方式,由于他最近很忙,因此需要请你帮他解决这个问题。
输入描述:
1 2 3 4 5 6 7 8 9 10
第一行输入一个正整数 N,表示队列的大小。 第二行输入 N 个正整数,Q1, Q2, Q3, ... ..., QN,Qi 表示队列中的第 i 个元素。保证这 N 个数是 N 的一个全排列。 第三行输入一个正整数 P,表示接下来要进行的操作次数。
接下来 P 行,第 i 行输入一个字符串 Si 以及一个正整数 Xi,表示一次操作。 1 ≤ N ≤ 105. 1 ≤ Qi ≤ N. 1 ≤ P ≤ 105. Si { “FIRST”, “LAST” }. 1 ≤ Xi ≤ 105.
Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.